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 pairof sets intersecting. The celebrated theorem of Erdos-Ko-Rado from 1961 saysthat 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 ina set system of larger size. Except for the case k=2, solved by Ahlswede andKatona, this problem has remained open for the last three decades. In this paper, we determine the minimum number of disjoint pairs in smallk-uniform families, thus confirming a conjecture of Bollobas and Leader inthese cases. Moreover, we obtain similar results for two well-known extensionsof the Erdos-Ko-Rado theorem, determining the minimum number of matchings ofsize q and the minimum number of t-disjoint pairs that appear in set systemslarger than the corresponding extremal bounds. In the latter case, thisprovides a partial solution to a problem of Kleitman and West.