Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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?)


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
Email: mubayi@math.uic.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-06-04009-8
PII: S 0002-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