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

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ózsef Balogh, Béla Bollobás, and Miklós Simonovits,*The number of graphs without forbidden subgraphs*, J. Combin. Theory Ser. B**91**(2004), no. 1, 1–24. MR**2047528**, 10.1016/j.jctb.2003.08.001**2.**J.-C. Bermond and P. Frankl,*On a conjecture of Chvátal on 𝑚-intersecting hypergraphs*, Bull. London Math. Soc.**9**(1977), no. 3, 310–312. MR**0457287****3.**V. Chvátal,*An extremal set-intersection theorem*, J. London Math. Soc. (2)**9**(1974/75), 355–359. MR**0354388****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. Erdős, Chao Ko, and R. Rado,*Intersection theorems for systems of finite sets*, Quart. J. Math. Oxford Ser. (2)**12**(1961), 313–320. MR**0140419****6.**P. Erdős, D. J. Kleitman, and B. L. Rothschild,*Asymptotic enumeration of 𝐾_{𝑛}-free graphs*, Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973) Accad. Naz. Lincei, Rome, 1976, pp. 19–27. Atti dei Convegni Lincei, No. 17 (English, with Italian summary). MR**0463020****7.**P. Frankl,*On Sperner families satisfying an additional condition*, J. Combinatorial Theory Ser. A**20**(1976), no. 1, 1–11. MR**0398842****8.**Peter Frankl,*On a problem of Chvátal and Erdős on hypergraphs containing no generalized simplex*, J. Combin. Theory Ser. A**30**(1981), no. 2, 169–182. MR**611249**, 10.1016/0097-3165(81)90004-2**9.**P. Frankl and Z. Füredi,*Exact solution of some Turán-type problems*, J. Combin. Theory Ser. A**45**(1987), no. 2, 226–262. MR**894820**, 10.1016/0097-3165(87)90016-1**10.**Z. Füredi,*Hypergraphs in which all disjoint pairs have distinct unions*, Combinatorica**4**(1984), no. 2-3, 161–168. MR**771723**, 10.1007/BF02579216**11.**Zoltán Füredi and Miklós Simonovits,*Triple systems not containing a Fano configuration*, Combin. Probab. Comput.**14**(2005), no. 4, 467–484. MR**2160414**, 10.1017/S0963548305006784**12.**A. J. W. Hilton and E. C. Milner,*Some intersection theorems for systems of finite sets*, Quart. J. Math. Oxford Ser. (2)**18**(1967), 369–384. MR**0219428****13.**Peter Keevash and Benny Sudakov,*On a hypergraph Turán problem of Frankl*, Combinatorica**25**(2005), no. 6, 673–706. MR**2199431**, 10.1007/s00493-005-0042-2**14.**Peter Keevash and Benny Sudakov,*The Turán number of the Fano plane*, Combinatorica**25**(2005), no. 5, 561–574. MR**2176425**, 10.1007/s00493-005-0034-2**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.**Dhruv Mubayi and Jacques Verstraëte,*A hypergraph extension of the bipartite Turán problem*, J. Combin. Theory Ser. A**106**(2004), no. 2, 237–253. MR**2021684**, 10.1016/j.jcta.2004.02.002**18.**Dhruv Mubayi and Jacques Verstraëte,*Proof of a conjecture of Erdős on triangles in set-systems*, Combinatorica**25**(2005), no. 5, 599–614. MR**2176427**, 10.1007/s00493-005-0036-0**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**, 10.1016/j.jcta.2004.05.005**21.**M. Simonovits,*A method for solving extremal problems in graph theory, stability problems*, Theory of Graphs (Proc. Colloq., Tihany, 1966) Academic Press, New York, 1968, pp. 279–319. MR**0233735**

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:
http://dx.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