Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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 $ A, B, C$ such that $ A \cap B$, $ B \cap C$, $ C \cap A$ are each nonempty, and $ A \cap B \cap C= \emptyset$. We prove the following new theorem about the stability of triangle-free set systems.

Fix $ r\ge 3$. For every $ \delta >0$, there exist $ \epsilon>0$ and $ n_0=n_0(\epsilon, r)$ such that the following holds for all $ n>n_0$: if $ \vert X\vert=n$ and $ \mathcal{G}$ is a triangle-free family of $ r$-sets of $ X$ containing at least $ (1-\epsilon){n-1 \choose r-1}$ members, then there exists an $ (n-1)$-set $ S \subset X$ which contains fewer than $ \delta{n-1 \choose r-1}$ members of $ \mathcal{G}$.

This is one of the first stability theorems for a nontrivial problem in extremal set theory. Indeed, the corresponding extremal result, that for $ n \ge 3r/2>4$ every triangle-free family $ \mathcal{G}$ of $ r$-sets of $ X$ has size at most $ {n-1 \choose r-1}$, was a longstanding conjecture of Erdos (open since 1971) that was only recently settled by Mubayi and Verstraëte (2005) for all $ n\ge 3r/2$.

References [Enhancements On Off] (What's this?)

  • 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 $ m$-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 $ K_{n}$-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 $ k$-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 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)

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 60607-7045

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

American Mathematical Society