论文标题
没有完美匹配的家庭
Families with no perfect matchings
论文作者
论文摘要
我们认为$ k $ -subsets的$ \ {1，\ dots，n \} $的家庭，其中$ n $是$ k $的倍数，没有完美的匹配。对于没有完美匹配的家庭$ \ mathcal {f} $的同等条件是要有一个阻止集，这是一组$ \ {1，\ dots，n \} $的$ b $元素，该元素在$ \ mathcal {f} $中无法由$ b $ disconse我们对家庭$ \ Mathcal {f} $的最大尺寸特别感兴趣，没有完美的匹配，也没有小于$ b $的大小的阻止集。弗兰克尔（Frankl）解决了没有单身封锁集的家庭（换句话说，$ b = 2 $ case），以实现足够大的$ n $，并猜想了一般$ b $的最佳结构。尽管Frankl的构造对$ k = 2，3 $无法最佳，但我们表明，每当$ k \ ge 100 $和$ n $都足够大时，构造都是最佳的。
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.
