Set systems with few disjoint pairs (Q1878795): Difference between revisions

An old theorem of \textit{P. Frankl} [J. Comb. Theory, Ser. A 22, 249--251 (1977; Zbl 0363.05010)] and \textit{R. Ahlswede} [J. Comb. Theory, Ser. B 28, 164--167 (1980; Zbl 0441.05036)] states that any set system with at least \(\left | [n]^{\geq r} \right | \) elements has at least as many disjoint pairs as the set system \([n]^{\geq r}.\) This paper gives a new proof of this fact as well as a fairly good lower bound on the minimum number of disjoint pairs as a function of the size of a general system. The main tool of the proof is the new notion of a fractional set system.