Triangle-intersecting families of graphs
Ehud Friedgut
Hebrew University, Jerusalem, IsraelDavid Ellis
St John's College, Cambridge, UKYuval Filmus
University of Toronto, Toronto, Canada
![Triangle-intersecting families of graphs cover](/_next/image?url=https%3A%2F%2Fcontent.ems.press%2Fassets%2Fpublic%2Fimages%2Fserial-issues%2Fcover-jems-volume-14-issue-3.png&w=3840&q=90)
Abstract
A family of graphs is triangle-intersecting if for every , 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 vertices are those obtained by fixing a specific triangle and taking all graphs containing it, resulting in a family of size . 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