JournalsjemsVol. 14, No. 3pp. 841–885

Triangle-intersecting families of graphs

  • Ehud Friedgut

    Hebrew University, Jerusalem, Israel
  • David Ellis

    St John's College, Cambridge, UK
  • Yuval Filmus

    University of Toronto, Toronto, Canada
Triangle-intersecting families of graphs cover
Download PDF

Abstract

A family F\mathcal F of graphs is triangle-intersecting if for every G,HFG,H\in\mathcal F, GHG \cap H contains a triangle. A conjecture of Simonovits and Sós from 1976 states that the largest triangle-intersecting families of graphs on a fixed set of nn vertices are those obtained by fixing a specific triangle and taking all graphs containing it, resulting in a family of size 182(n2)\frac{1}{8}2^{\binom{n}{2}}. We prove this conjecture and some generalizations (for example, we prove that the same is true of odd-cycle-intersecting families, and we obtain best possible bounds on the size of the family under different, not necessarily uniform, measures). We also obtain stability results, showing that almost-largest triangle-intersecting families have approximately the same structure.

Cite this article

Ehud Friedgut, David Ellis, Yuval Filmus, Triangle-intersecting families of graphs. J. Eur. Math. Soc. 14 (2012), no. 3, pp. 841–885

DOI 10.4171/JEMS/320