2020/01/06 by Currier, Gabriel
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2001.01812
A d-simplex is defined to be a collection A1,…,Ad+1 of subsets of size k of [n] such that the intersection of all of them is empty, but the intersection of any d of them is non-empty. Furthermore, a d-cluster is a collection of d+1 such sets with empty intersection and union of size ≤ 2k, and a d-simplex-cluster is such a collection that is both a d-simplex and a d-cluster. The Erdős-Chvátal d-simplex Conjecture from 1974 states that any family of k-subsets of [n] containing no d-simplex must be of size no greater than n -1 \choose k-1. In 2011, Keevash and Mubayi extended this conjecture by hypothesizing that the same bound would hold for families containing no d-simplex-cluster. In this paper, we resolve Keevash and Mubayi's conjecture for all 4 ≤ d+1 ≤ k and n ≥ 2k-d+2, which in turn resolves all remaining cases of the Erdős-Chvátal Conjecture except when n is very small (i.e. n < 2k-d+2).