Combinatorics, Probability and Computing

Table of Contents - 2009 - Volume 18, Issue 03  

Cambridge Journals Online - CUP Full-Text Page
Combinatorics, Probability and Computing (2009), 18:441-454 Cambridge University Press
Copyright © Cambridge University Press 2009
doi:10.1017/S0963548309009705

Paper

Simplex Stability

DHRUV MUBAYIa1 c1 and RESHMA RAMADURAIa2

a1 Department of Mathematics, Statistics and Computer Science, University of Illinois, Chicago, Illinois 60607, USA (e-mail: mubayi@math.uic.edu)
a2 Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213-3890, USA (e-mail: rramadur@andrew.cmu.edu)
Article author query
mubayi d [Google Scholar]
ramadurai r [Google Scholar]

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 $|\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 xs03F5 < 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 xs2229j≠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, xs03F5 = 0 and n ≥ 2k.

(Received December 31 2007)

(Revised November 05 2008)

(Online publication February 19 2009)

Correspondence:

c1 Research partially supported by NSF grant DMS 0653946, and an Alfred P. Sloan Research Fellowship.