论文标题
无冲突的超图匹配
Conflict-free hypergraph matchings
论文作者
论文摘要
著名的Pippenger定理，Frankl和Rödl指出，每个几乎规范，统一的HyperGraph $ \ Mathcal {H} $，最大Codegree都具有几乎完美的匹配。我们通过获得``无冲突''匹配来扩展了此结果，其中冲突是通过集合的$ \ Mathcal {c} $ subsets $ c \ subseteq e（\ Mathcal {H}）$编码的。我们说，如果$ \ Mathcal {M {M} $不包含$ \ Mathcal {C} $的元素，则匹配的$ \ Mathcal {M} \ subseteq e（\ Mathcal {h}）$是无冲突的。在$ \ Mathcal {C} $上的自然假设下，我们证明$ \ Mathcal {H} $具有无冲突，几乎完美的匹配。这有许多应用程序，其中之一为所谓的``高登山''系统产生了新的渐近结果。我们的主要工具是一种随机的贪婪算法，我们称之为``无冲突的匹配过程''。
A celebrated theorem of Pippenger, and Frankl and Rödl states that every almost-regular, uniform hypergraph $\mathcal{H}$ with small maximum codegree has an almost-perfect matching. We extend this result by obtaining a ``conflict-free'' matching, where conflicts are encoded via a collection $\mathcal{C}$ of subsets $C\subseteq E(\mathcal{H})$. We say that a matching $\mathcal{M}\subseteq E(\mathcal{H})$ is conflict-free if $\mathcal{M}$ does not contain an element of $\mathcal{C}$ as a subset. Under natural assumptions on $\mathcal{C}$, we prove that $\mathcal{H}$ has a conflict-free, almost-perfect matching. This has many applications, one of which yields new asymptotic results for so-called ``high-girth'' Steiner systems. Our main tool is a random greedy algorithm which we call the ``conflict-free matching process''.
