Structure and stability of triangle-free set systems

Author:
Dhruv Mubayi

Journal:
Trans. Amer. Math. Soc. **359** (2007), 275-291

MSC (2000):
Primary 05C35, 05C65, 05D05

DOI:
https://doi.org/10.1090/S0002-9947-06-04009-8

Published electronically:
August 16, 2006

MathSciNet review:
2247891

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We define the notion of stability for a monotone property of set systems. This phenomenon encompasses some classical results in combinatorics, foremost among them the Erdos-Simonovits stability theorem. A triangle is a family of three sets such that , , are each nonempty, and . We prove the following new theorem about the stability of triangle-free set systems.

Fix . For every , there exist and such that the following holds for all : if and is a triangle-free family of -sets of containing at least members, then there exists an -set which contains fewer than members of .

This is one of the first stability theorems for a nontrivial problem in extremal set theory. Indeed, the corresponding extremal result, that for every triangle-free family of -sets of has size at most , was a longstanding conjecture of Erdos (open since 1971) that was only recently settled by Mubayi and Verstraëte (2005) for all .

**1.**J. Balogh, B. Bollobás, M. Simonovits, The number of graphs without forbidden subgraphs,*Journal of Combinatorial Theory, Series B.*, 91 (2004), no. 1, 1-24.MR**2047528 (2005b:05122)****2.**J.-C. Bermond, P. Frankl, On a conjecture of Chvátal on -intersecting hypergraphs.*Bull. London Math. Soc.*9 (1977), no. 3, 310-312. MR**0457287 (56:15495)****3.**V. Chvátal, An extremal set-intersection theorem,*J. London Math. Soc. (2)*9 (1974/75), 355-359. MR**0354388 (50:6867)****4.**P. Erdos, Topics in combinatorial analysis.*Proc. Second Louisiana Conf. on Comb., Graph Theory and Computing*(R. C. Mullin et al., eds.) pp. 2-20, Louisiana State Univ., Baton Rouge, 1971.**5.**P. Erdos, H. Ko, R. Rado, Intersection theorems for systems of finite sets.*Quart. J. Math. Oxford Ser. (2)*12 (1961), 313-320.MR**0140419 (25:3839)****6.**P. Erdos, D. J. Kleitman, B. L. Rothschild, Asymptotic enumeration of -free graphs. (English. Italian summary) Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo II, pp. 19-27. Atti dei Convegni Lincei, No. 17, Accad. Naz. Lincei, Rome, 1976.MR**0463020 (57:2984)****7.**P. Frankl, On Sperner families satisfying an additional condition,*J. Combin. Theory Ser. A*, 20 (1976), no. 1, 1-11.MR**0398842 (53:2693)****8.**P. Frankl, On a problem of Chvátal and Erdos on hypergraphs containing no generalized simplex.*J. Combin. Theory Ser. A*30 (1981), no. 2, 169-182. MR**0611249 (83k:05086)****9.**P. Frankl, Z. Füredi, Exact solution of some Turán-type problems,*J. Combin. Theory Ser. A*, 45 (1987), no. 2, 226-262. MR**0894820 (88h:05005)****10.**Z. Füredi, Hypergraphs in which all disjoint pairs have distinct unions.*Combinatorica*, 4 (1984), no. 2-3, 161-168. MR**0771723 (86c:05009)****11.**Z. Füredi, M. Simonovits, Triple systems not containing a Fano configuration,*Combin. Probab. Comput.*14 (2005), no. 4, 467-484. MR**2160414 (2006d:05034)****12.**A. J. W. Hilton, E. C. Milner, Some intersection theorems for systems of finite sets.*Quart. J. Math. Oxford Ser.*(2) 18 (1967), 369-384.MR**0219428 (36:2510)****13.**P. Keevash, B. Sudakov, On a hypergraph Turán problem of Frankl,*Combinatorica*, 25 (2005), no. 6, 673-706. MR**2199431****14.**P. Keevash, B. Sudakov, The Turán number of the Fano plane,*Combinatorica*, 25 (2005), no. 5, 561-574. MR**2176425 (2006f:05093)****15.**O. P. Lossers, P. Erdos, E. Milner,*Canad. Math Bull.*16 (1973), 145-146.**16.**D. Mubayi, O. Pikhurko, A new generalization of Mantel's theorem to -graphs, submitted.**17.**D. Mubayi, J. Verstraëte, A hypergraph extension of the bipartite Turán problem,*J. Combin. Theory Ser. A*, 106 (2004), no. 2, 237-253.MR**2021684 (2005b:05128)****18.**D. Mubayi, J. Verstraëte, Proof of a conjecture of Erdos on triangles in set-systems,*Combinatorica*, 25 (2005), no. 5, 599-614.MR**2176427****19.**O. Pikhurko, Exact computation of the hypergraph Turan function for expanded complete 2-graphs, 9 pp., accepted*J. Combin Theory Ser. B*, publication suspended for an indefinite time; see http://www.math.cmu.edu/ pikhurko/Copyright.html**20.**A. J. Sanders, Covering by intersecting families,*J. Combin. Theory Ser. A*108 (2004), no. 1, 51-61.MR**2087304 (2005d:05045)****21.**M. Simonovits, A method for solving extremal problems in graph theory, stability problems. 1968 Theory of Graphs (Proc. Colloq., Tihany, 1966) pp. 279-319, Academic Press, New York. MR**0233735 (38:2056)**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2000):
05C35,
05C65,
05D05

Retrieve articles in all journals with MSC (2000): 05C35, 05C65, 05D05

Additional Information

**Dhruv Mubayi**

Affiliation:
Department of Mathematics, Statistics, & Computer Science, University of Illinois at Chicago, 851 S. Morgan Street, Chicago, Illinois 60607-7045

Email:
mubayi@math.uic.edu

DOI:
https://doi.org/10.1090/S0002-9947-06-04009-8

Keywords:
Extremal set theory,
intersecting family,
stability theorems

Received by editor(s):
March 16, 2004

Received by editor(s) in revised form:
November 3, 2004

Published electronically:
August 16, 2006

Additional Notes:
The author was supported in part by NSF Grant DMS #0400812 and by an Alfred P. Sloan Research Fellowship.

Article copyright:
© Copyright 2006
by the author