Geodesic
Triangle-intersecting families of graphs
Journal of the European Mathematical Society, Tome 14 (2012) no. 3, pp. 841-885 Cet article a éte moissonné depuis la source EMS Press

Voir la notice de l'article

A family F of graphs is triangle-intersecting if for every G,H∈F, G∩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 81​2(2n​). 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.
DOI : 10.4171/jems/320
Classification : 05-XX, 00-XX
Keywords: Intersecting families, graphs, discrete Fourier analysis 
@article{JEMS_2012_14_3_a7,
     author = {David Ellis and Yuval Filmus and Ehud Friedgut},
     title = {Triangle-intersecting families of graphs},
     journal = {Journal of the European Mathematical Society},
     pages = {841--885},
     year = {2012},
     volume = {14},
     number = {3},
     doi = {10.4171/jems/320},
     url = {http://geodesic.mathdoc.fr/articles/10.4171/jems/320/}
}
TY  - JOUR
AU  - David Ellis
AU  - Yuval Filmus
AU  - Ehud Friedgut
TI  - Triangle-intersecting families of graphs
JO  - Journal of the European Mathematical Society
PY  - 2012
SP  - 841
EP  - 885
VL  - 14
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.4171/jems/320/
DO  - 10.4171/jems/320
ID  - JEMS_2012_14_3_a7
ER  - 
%0 Journal Article
%A David Ellis
%A Yuval Filmus
%A Ehud Friedgut
%T Triangle-intersecting families of graphs
%J Journal of the European Mathematical Society
%D 2012
%P 841-885
%V 14
%N 3
%U http://geodesic.mathdoc.fr/articles/10.4171/jems/320/
%R 10.4171/jems/320
%F JEMS_2012_14_3_a7
David Ellis; Yuval Filmus; Ehud Friedgut. Triangle-intersecting families of graphs. Journal of the European Mathematical Society, Tome 14 (2012) no. 3, pp. 841-885. doi: 10.4171/jems/320

Cité par Sources :