The maximum size of intersecting and union families of sets (Q657996): Difference between revisions

The well known Erdős-Ko-Rado theorem asserts that a pairwise intersection family of \(k\) element subsets of an \(n\) element set has size at most \(\binom{n - 1}{k - 1}\) if \(n \geq 2k\). In this paper the authors study some extensions of the above theorem. They consider the maximal size of families of \(k\)-element subsets of an \(n\) element set \(\{1,\dots,n\}\) that satisfy the properties that every \(r\) element subsets of the family have non-empty intersection, and no \(l\) subsets contain \(\{1, \dots, n\}\) in their union. The authors give upper estimations for the size of such a family. They prove that the size of such family is less then \(0.9\binom{n-2}{k-1}\) unless all subsets contain a given element, or all subsets miss a given element. The proof of this theorem is based on the Frankl's random walk method. The authors give a nice introduction to this method. They also study the weighted version of their results by proving an extension of the well known Kleitman inequality. The paper contains a few open problems, too.