关于彩虹匹配的稳定性

《Combinatorics, Probability and Computing》：On stability of rainbow matchings

k≥1时存在t0(k)，当t>t0(k)、max{k_i}≤k且n>2k(t+1)时，t+1个k_i-均匀超图族要么有t+1大小彩虹匹配，要么存在与每个超图相交的t元集W。该结果扩展了Hilton-Milner定理，并推广了Frankl-Kupavskii的稳定性结论至大n情形。

　　

摘要

我们证明了对于任意整数 $k \ge 1$，存在一个整数 $t_0(k)$，使得对于满足以下条件的整数 $t, k_1, \ldots, k_{t+1}, n$（其中 $t > t_0(k)$，$\max \{k_1, \ldots, k_{t+1} \le k$，且 $n > 2k(t+1)$）：如果 $F_i$ 是一个具有顶点集 $[n]$ 且对于所有 $i \in [t+1]$ 都有超过 $\binom{n}{k_i} - \binom{n-t}{k_i} - \binom{n-t-k}{k_i-1} + 1$ 条边的 $k_i$-一致超图，那么要么 $\{F_1, \ldots, F_{t+1\}$ 存在一个大小为 $t+1$ 的彩虹匹配，要么存在一个集合 $W \in \binom{[n]}{t}$，使得 $W$ 与所有的 $F_i$ 相交（对于所有 $i \in [t+1]$）。这可以看作是经典 Hilton-Milner 定理的彩虹非一致扩展。我们还证明了对于每一个 $t$ 和 $n > 2k^3t$，同样的结论也成立，这推广了 Frankl 和 Kupavskii 关于匹配的稳定性结果。

---

---

脚注

*

部分由中国国家自然科学基金（项目编号：12271425）支持

?

部分由中国国家重点研发计划（项目编号：2022YFA1006400）、中国国家自然科学基金（项目编号：12571376 和 12201400）以及上海市教育委员会（项目编号：2024AIYB003）支持

?

部分由美国国家科学基金会（NSF）的资助项目 DMS-1954134 和 DMS-2348702 支持

---