Combinatorial Theory

We consider families of \(k\)-subsets of \(\{1, \dots, n\}\), where \(n\) is a multiple of \(k\), which have no perfect matching. An equivalent condition for a family \(\mathcal{F}\) to have no perfect matching is for there to be a blocking set, which is a set of \(b\) elements of \(\{1, \dots, n\}\) that cannot be covered by \(b\) disjoint sets in \(\mathcal{F}\). We are specifically interested in the largest possible size of a family \(\mathcal{F}\) with no perfect matching and no blocking set of size less than \(b\). Frankl resolved the case of families with no singleton blocking set (in other words, the \(b=2\) case) for sufficiently large \(n\) and conjectured an optimal construction for general \(b\). Though Frankl's construction fails to be optimal for \(k = 2, 3\), we show that the construction is optimal whenever \(k \ge 100\) and \(n\) is sufficiently large.

Mathematics Subject Classifications: 05D05