×

zbMATH — the first resource for mathematics

Triangle-intersecting families of graphs. (English) Zbl 1238.05143
Summary: 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.

MSC:
05C35 Extremal problems in graph theory
05C75 Structural characterization of families of graphs
05D99 Extremal combinatorics
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Ahlswede, R., Khachatrian, L. H.: The complete intersection theorem for systems of finite sets. Eur. J. Combin. 18, 125-136 (1997) · Zbl 0869.05066
[2] Alon, N.: Personal communication. Erzsébet Bridge, Buda (August 1999)
[3] Christofides, D.: Personal communication (August 2010)
[4] Chung, F. R. K., Graham, R. L., Frankl, P., Shearer, J. B.: Some intersection theorems for ordered sets and graphs. J. Combin. Theory Ser. A 43, 23-37 (1986) · Zbl 0655.05001
[5] Ellis, D., Friedgut, E., Pilpel, H.: Intersecting families of permutations. J. Amer. Math. Soc. 24, 649-682 (2011) · Zbl 1285.05171
[6] Erd\Acute\Acute os, P., Ko, C., Rado, R.: Intersection theorems for systems of finite sets. Quart. J. Math. 2, 313-320 (1961) · Zbl 0100.01902
[7] Frankl, P.: The shifting technique in extremal set theory. In: Surveys in Combina- torics, London Math. Soc. Lecture Note Ser. 123, Cambridge Univ. Press, 81-110 (1987) · Zbl 0633.05038
[8] Friedgut, E.: On the measure of intersecting families, uniqueness and stability. Combinatorica 28, 503-528 (2008) · Zbl 1199.05319
[9] Füredi, Z., Griggs, J. R., Holzman, R., Kleitman, D. J.: Representations of families of triples over gf(2). J. Combin. Theory Ser. A 53, 306-315 (1990) · Zbl 0739.05015
[10] Griggs, J. R., Walker, J. W.: Anticlusters and intersecting families of subsets. J. Combin. Theory Ser. A 51, 90-103 (1989) · Zbl 0722.05003
[11] Hoffman, A. J.: On eigenvalues and colorings of graphs. In: Graph Theory and its Applications (Madison, WI), Academic Press, New York, 79-9 (1969) · Zbl 0221.05061
[12] Hook, D. G., McAree, P. R.: Using Sturm sequences to bracket real roots of polynomial equa- tions. In: A. Glassner (ed.), Graphic Gems I, Academic Press, 416-422 (1990)
[13] Kindler, G., Safra, S.: Noise-resistant boolean-functions are juntas.
[14] Nisan, N., Szegedy, M.: On the degree of boolean functions as real polynomials. Comput. Complexity 4, 301-313 (1994) · Zbl 0829.68047
[15] Russell, P. A.: Families intersecting on an interval. Discrete Math. 309, 2952-2956 (2009) · Zbl 1194.05155
[16] Wilson, R. M.: The exact bound in the Erd\Acute\Acute os-Ko-Rado theorem. Combinatorica 4, 247-257 (1984) · Zbl 0556.05039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.