2013/05/29 by Shagnik Das, Das, Shagnik, Wenying Gan +3 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1305.6715
28 pages
arxiv created 2013/05/29 · arxiv updated 2013/05/30
Let F be a set system on [n] with all sets having k elements and every pair of sets intersecting. The celebrated theorem of Erdos-Ko-Rado from 1961 says that any such system has size at most n-1 \choose k-1. A natural question, which was asked by Ahlswede in 1980, is how many disjoint pairs must appear in a set system of larger size. Except for the case k=2, solved by Ahlswede and Katona, this problem has remained open for the last three decades. In this paper, we determine the minimum number of disjoint pairs in small k-uniform families, thus confirming a conjecture of Bollobas and Leader in these cases. Moreover, we obtain similar results for two well-known extensions of the Erdos-Ko-Rado theorem, determining the minimum number of matchings of size q and the minimum number of t-disjoint pairs that appear in set systems larger than the corresponding extremal bounds. In the latter case, this provides a partial solution to a problem of Kleitman and West.