Triangle-intersecting Families of Graphs
By David Ellis, Yuval Filmus, Ehud Friedgut. 2010
81 citations recorded by the source corpus.
A family of graphs F is triangle-intersecting if for every G,H 2 F, G\H contains a triangle. A conjecture of Simonovits and Sos 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 1 2 ( 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 dierent, not necessarily uniform, measures). We also obtain stability results, showing that almost-largest triangle-intersecting families have approximately the same structure.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics
View Paper: https://www.semanticscholar.org/paper/ade77f053c569605adb98ffbb34c23e222e059fa
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
Citations in the corpus
- Stability versions of Erdős–Ko–Rado type theorems via isoperimetry (2016, background): “Specifically, for t = 1 we can obtain the assertion of Proposition 3.4 using a theorem of Nayar [51], which is a p-biased version of the Friedgut-KalaiNaor (FKN) theorem [31].”
- Three tutorial lectures on entropy and counting (2014, unknown): “Recently Ellis, Filmus and Friedgut [18] used discrete Fourier analysis to obtain the sharp bound |G| ≤ 2( n 2 ) − 3 that had been conjectured by Simonovits and S´os.”