The minimum number of disjoint pairs in set systems and related problems
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 and Rado from 1961 says that, provided n 2k, any such system has size at most (_{k 1}{n 1}(k 1n 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.
Comb.