Triangle-intersecting families of graphs

Abstract

A family $\mathcal{F}$ of graphs is triangle-intersecting if for every $G,H\in \mathcal{F}$, $G\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 $n$ vertices are those obtained by fixing a specific triangle and taking all graphs containing it, resulting in a family of size $\frac{1}{8}{2}^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$. 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.