论文标题
在彩虹匹配的猜想上
On the rainbow matching conjecture for 3-uniform hypergraphs
论文作者
论文摘要
Aharoni和Howard，以及独立的Huang，Loh和Sudakov提出了以下彩虹版本的ERDS匹配猜想：对于积极的整数$ n，k，m $，$ n \ ge km $，如果每个家庭$ f_1，f_1，\ ldots，\ ldots，\ ldots，\ ldots，f_m \ seteq {n] $\max\{\binom{n}{k} - \binom{n-m+1}{k}, \binom{km-1}{k}\}$, then there exist pairwise disjoint subsets $e_1,\dots, e_m$ such that $e_i\in F_i$ for all $i\in [m]$.我们证明存在绝对常数$ n_0 $，因此该彩虹版本以$ k = 3 $和$ n \ geq n_0 $保存。我们将这个彩虹匹配的问题转换为特殊的HyperGraph $ h $上的匹配问题。然后，我们将几种现有技术结合在统一超图中的比赛中：在$ h $中找到一个吸收的匹配$ m $；使用Alon等人的随机过程。找到几乎常规的子图$ H-V（m）$；并在$ H-V（M）$中找到几乎完美的匹配。为了完成该过程，我们还需要证明在3-均匀的超图中的比赛中获得新的结果，这可以看作是oluczak和Mieczkowska结果的稳定版本，并且可能具有独立的利益。
Aharoni and Howard, and, independently, Huang, Loh, and Sudakov proposed the following rainbow version of Erdős matching conjecture: For positive integers $n,k,m$ with $n\ge km$, if each of the families $F_1,\ldots, F_m\subseteq {[n]\choose k}$ has size more than $\max\{\binom{n}{k} - \binom{n-m+1}{k}, \binom{km-1}{k}\}$, then there exist pairwise disjoint subsets $e_1,\dots, e_m$ such that $e_i\in F_i$ for all $i\in [m]$. We prove that there exists an absolute constant $n_0$ such that this rainbow version holds for $k=3$ and $n\geq n_0$. We convert this rainbow matching problem to a matching problem on a special hypergraph $H$. We then combine several existing techniques on matchings in uniform hypergraphs: find an absorbing matching $M$ in $H$; use a randomization process of Alon et al. to find an almost regular subgraph of $H-V(M)$; and find an almost perfect matching in $H-V(M)$. To complete the process, we also need to prove a new result on matchings in 3-uniform hypergraphs, which can be viewed as a stability version of a result of Łuczak and Mieczkowska and might be of independent interest.
