# 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

## 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^{\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