Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-06T22:49:55.241Z 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: mubayi@math.uic.edu)
RESHMA RAMADURAI
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213-3890, USA (e-mail: rramadur@andrew.cmu.edu)
*
†Research partially supported by NSF grant DMS 0653946, and an Alfred P. Sloan Research Fellowship.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 $|\cG| \geq (1 - o(1))\binom{n-1 }{k-1}$, 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 $|\cG| > (1 + \epsilon)\binom{n-1 }{ k-1}$ 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.

Information

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

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