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 .
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 , who proved it for d = 1, = 0 and n ≥ 2k.
(Received December 31 2007)
(Revised November 05 2008)
(Online publication February 19 2009)
c1 Research partially supported by NSF grant DMS 0653946, and an Alfred P. Sloan Research Fellowship.