Skip to main content
eScholarship
Open Access Publications from the University of California

Combinatorial Theory

Combinatorial Theory banner

Families with no perfect matchings

  • Author(s): Singhal, Mihir
  • et al.

Published Web Location

https://doi.org/10.5070/C61055359Creative Commons 'BY' version 4.0 license
Abstract

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

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View