Structure and stability of trianglefree set systems
Author:
Dhruv Mubayi
Journal:
Trans. Amer. Math. Soc. 359 (2007), 275291
MSC (2000):
Primary 05C35, 05C65, 05D05
Published electronically:
August 16, 2006
MathSciNet review:
2247891
Fulltext 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 ErdosSimonovits 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 trianglefree set systems. Fix . For every , there exist and such that the following holds for all : if and is a trianglefree 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 trianglefree 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 (2005b:05122), http://dx.doi.org/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
(56 #15495)
 3.
V.
Chvátal, An extremal setintersection 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. 220, 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
(25 #3839)
 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
(57 #2984)
 7.
P.
Frankl, On Sperner families satisfying an additional
condition, J. Combinatorial Theory Ser. A 20 (1976),
no. 1, 1–11. MR 0398842
(53 #2693)
 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
(83k:05086), http://dx.doi.org/10.1016/00973165(81)900042
 9.
P.
Frankl and Z.
Füredi, Exact solution of some Turántype
problems, J. Combin. Theory Ser. A 45 (1987),
no. 2, 226–262. MR 894820
(88h:05005), http://dx.doi.org/10.1016/00973165(87)900161
 10.
Z.
Füredi, Hypergraphs in which all disjoint pairs have distinct
unions, Combinatorica 4 (1984), no. 23,
161–168. MR
771723 (86c:05009), http://dx.doi.org/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
(2006d:05034), http://dx.doi.org/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
(36 #2510)
 13.
Peter
Keevash and Benny
Sudakov, On a hypergraph Turán problem of Frankl,
Combinatorica 25 (2005), no. 6, 673–706. MR 2199431
(2006j:05142), http://dx.doi.org/10.1007/s0049300500422
 14.
Peter
Keevash and Benny
Sudakov, The Turán number of the Fano plane,
Combinatorica 25 (2005), no. 5, 561–574. MR 2176425
(2006f:05093), http://dx.doi.org/10.1007/s0049300500342
 15.
O. P. Lossers, P. Erdos, E. Milner, Canad. Math Bull. 16 (1973), 145146.
 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
(2005b:05128), http://dx.doi.org/10.1016/j.jcta.2004.02.002
 18.
Dhruv
Mubayi and Jacques
Verstraëte, Proof of a conjecture of Erdős on triangles
in setsystems, Combinatorica 25 (2005), no. 5,
599–614. MR 2176427
(2006g:05215), http://dx.doi.org/10.1007/s0049300500360
 19.
O. Pikhurko, Exact computation of the hypergraph Turan function for expanded complete 2graphs, 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), http://dx.doi.org/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
(38 #2056)
 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, 124.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, 310312. MR 0457287 (56:15495)
 3.
 V. Chvátal, An extremal setintersection theorem, J. London Math. Soc. (2) 9 (1974/75), 355359. 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. 220, 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), 313320.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. 1927. 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, 111.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, 169182. MR 0611249 (83k:05086)
 9.
 P. Frankl, Z. Füredi, Exact solution of some Turántype problems, J. Combin. Theory Ser. A, 45 (1987), no. 2, 226262. MR 0894820 (88h:05005)
 10.
 Z. Füredi, Hypergraphs in which all disjoint pairs have distinct unions. Combinatorica, 4 (1984), no. 23, 161168. MR 0771723 (86c:05009)
 11.
 Z. Füredi, M. Simonovits, Triple systems not containing a Fano configuration, Combin. Probab. Comput. 14 (2005), no. 4, 467484. 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), 369384.MR 0219428 (36:2510)
 13.
 P. Keevash, B. Sudakov, On a hypergraph Turán problem of Frankl, Combinatorica, 25 (2005), no. 6, 673706. MR 2199431
 14.
 P. Keevash, B. Sudakov, The Turán number of the Fano plane, Combinatorica, 25 (2005), no. 5, 561574. MR 2176425 (2006f:05093)
 15.
 O. P. Lossers, P. Erdos, E. Milner, Canad. Math Bull. 16 (1973), 145146.
 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, 237253.MR 2021684 (2005b:05128)
 18.
 D. Mubayi, J. Verstraëte, Proof of a conjecture of Erdos on triangles in setsystems, Combinatorica, 25 (2005), no. 5, 599614.MR 2176427
 19.
 O. Pikhurko, Exact computation of the hypergraph Turan function for expanded complete 2graphs, 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, 5161.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. 279319, Academic Press, New York. MR 0233735 (38:2056)
Similar Articles
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 606077045
Email:
mubayi@math.uic.edu
DOI:
http://dx.doi.org/10.1090/S0002994706040098
PII:
S 00029947(06)040098
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
