Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-25T19:49:19.325Z Has data issue: false hasContentIssue false
  • English
  • Français

Simplex Stability

Published online by Cambridge University Press:  01 May 2009

DHRUV MUBAYI  and
RESHMA RAMADURAI
DHRUV MUBAYI*
Affiliation:
Department of Mathematics, Statistics and Computer Science, University of Illinois, Chicago, Illinois 60607, USA (e-mail: [email protected])
RESHMA RAMADURAI
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213-3890, USA (e-mail: [email protected])
*
†Research partially supported by NSF grant DMS 0653946, and an Alfred P. Sloan Research Fellowship.
Get access Rights & Permissions [Opens in a new window]

Abstract

A d-simplex is a collection of d + 1 sets such that every d of them has non-empty intersection and the intersection of all of them is empty. Fix k ≥ d + 2 ≥ 3 and let be a family of k-element subsets of an n-element set that contains no d-simplex. We prove that if , then there is a vertex x of such that the number of sets in omitting x is o(nk−1) (here o(1)→ 0 and n → ∞). A similar result when n/k is bounded from above was recently proved in [10].

Our main result is actually stronger, and implies that if for any ϵ < 0 and n sufficiently large, then contains d + 2 sets A, A1, . . . ,Ad+1 such that the Ais form a d-simplex, and A contains an element of ∩j≠iAj for each i. This generalizes, in asymptotic form, a recent result of Vestraëte and the first author [18], who proved it for d = 1, ϵ = 0 and n ≥ 2k.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 3 , May 2009 , pp. 441 - 454
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Chvátal, V. (1974/75) An extremal set-intersection theorem. J. London Math. Soc. 9 355–359.CrossRefGoogle Scholar
[2]Erdős, P. (1971) Topics in combinatorial analysis. In Proc. 2nd Louisiana Conf. on Comb., Graph Theory and Computing (Mullin, R. C. et al. , eds), Louisiana State University, Baton Rouge, pp 2–20.Google Scholar
[3]Erdős, P., Ko, H. and Rado, R. (1961) Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. 12 313–320.CrossRefGoogle Scholar
[4]Frankl, P. (1995) Handbook of Combinatorics (Graham, R., Grötschel, M. and Lovász, L., eds), Elsevier Science, Chapter 24, pp. 1317.Google Scholar
[5]Frankl, P. and Füredi, Z. (1983) A new generalization of the Erdős–Ko–Rado theorem. Combinatorica 3 341–349.CrossRefGoogle Scholar
[6]Füredi, Z. and Ozkahya, L. An intersection theorem with small unions. Preprint.Google Scholar
[7]Füredi, Z. and Simonovits, M. (2005) Triple systems not containing a Fano configuration. Combin. Probab. Comput. 14 467–484CrossRefGoogle Scholar
[8]Keevash, P. (2005) The Turán problem for projective geometries. J. Combin. Theory Ser. A 111 289–309.CrossRefGoogle Scholar
[9]Keevash, P. and Mubayi, D. (2004) Stability theorems for cancellative hypergraphs. J. Combin. Theory Ser. B 92 163–175.CrossRefGoogle Scholar
[10]Keevash, P. and Mubayi, D. Set systems without a simplex or a cluster. Combinatorica, to appear.Google Scholar
[11]Keevash, P. and Sudakov, B. (2005) The Turán number of the Fano plane. Combinatorica 25 561–574.CrossRefGoogle Scholar
[12]Keevash, P. and Sudakov, B. (2005) On a hypergraph Turán problem of Frankl. Combinatorica 25 673–706.CrossRefGoogle Scholar
[13]Mubayi, D. (2006) Erdős–Ko–Rado for three sets. J. Combin. Theory Ser. A 113 547–550.CrossRefGoogle Scholar
[14]Mubayi, D. (2007) Structure and stability of triangle-free set systems. Trans. Amer. Math. Soc. 359 275–291.CrossRefGoogle Scholar
[15]Mubayi, D. (2007) An intersection theorem for four sets. Adv. Math. 215 601–615.CrossRefGoogle Scholar
[16]Mubayi, D. and Ramadurai, R. Set systems with union and intersection constraints. J. Combin. Theory Ser. B, to appear.Google Scholar
[17]Mubayi, D. and Verstraëte, J. (2005) Proof of a conjecture of Erdős on triangles in set systems. Combinatorica 25 599–614.CrossRefGoogle Scholar
[18]Mubayi, D. and Verstraëte, J. (2007) Minimal paths and cycles in set systems. Europ. J. Combin. 28 1681–1693.CrossRefGoogle Scholar
[19]Mubayi, D. and Verstraëte, J. Two-regular subgraphs of hypergraphs. J. Combin. Theory Ser. B, to appear.Google Scholar
[20]Simonovits, M. (1968) A method for solving extremal problems in graph theory, stability problems. In Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, pp. 279–319.Google Scholar