论文标题
在超图中找到几乎完美的匹配，避免了禁止的匹配
Finding an almost perfect matching in a hypergraph avoiding forbidden submatchings
论文作者
论文摘要
1973年，埃尔德（Erd）猜想了高腰带$（n，3,2）$ -Steiner Systems的存在。最近，格洛克（Glock），库恩（Kühn），卢（Kühn），奥斯图斯（Osthus）以及独立的博曼（Bohman）和沃恩克（Warnke）证明了埃尔德（Erd）的猜想的大概版本。就在今年，Kwan，SAH，Sawhney和Simkin证明了Erdős的猜想。至于具有更通用参数的Steiner系统，Glock，Kühn，Lo和Osthus猜想了高环绕$（N，Q，R）$ -Steiner Systems的存在。我们证明了他们的猜想的大致版本。 该结果来自我们的一般主要结果，这些结果涉及在HyperGraph $ G $中找到完美或几乎完美的匹配，以避免给定的一组匹配（我们将其视为HyperGraph $ h $，其中$ v（h）= e（g）$）。我们的第一个主要结果是对Pippenger的经典定理（用于找到几乎完美的匹配）以及Ajtai，Komlós，Pintz，Spencer和Szemerédi（用于在Girth五五五颗五颗摄影中找到独立集）。更一般而言，我们证明了这一点用于着色，甚至列出着色，并将其进一步推广到$ h $是带有小型代码的超图（对于高腰带设计是一个特定的实例）。的确，我们结果的着色版本甚至可以将几乎$ k_n^r $的分区分成近似的高腰带$（n，q，r）$ - 施泰纳系统。 我们的主要结果还意味着在两部分超图中存在完美的匹配，其中零件具有略有不平衡的度。这有许多应用程序；例如，它证明了在Kahn定理的设置中存在$δ$成对的脱节列表。它还证明了各种彩虹匹配的渐近版本在稀疏设置中结果（在这种情况下，颜色的数量可能比颜色数量小得多），甚至在这种情况下存在许多成对分离的彩虹匹配。
In 1973, Erdős conjectured the existence of high girth $(n,3,2)$-Steiner systems. Recently, Glock, Kühn, Lo, and Osthus and independently Bohman and Warnke proved the approximate version of Erdős' conjecture. Just this year, Kwan, Sah, Sawhney, and Simkin proved Erdős' conjecture. As for Steiner systems with more general parameters, Glock, Kühn, Lo, and Osthus conjectured the existence of high girth $(n,q,r)$-Steiner systems. We prove the approximate version of their conjecture. This result follows from our general main results which concern finding perfect or almost perfect matchings in a hypergraph $G$ avoiding a given set of submatchings (which we view as a hypergraph $H$ where $V(H)=E(G)$). Our first main result is a common generalization of the classical theorems of Pippenger (for finding an almost perfect matching) and Ajtai, Komlós, Pintz, Spencer, and Szemerédi (for finding an independent set in girth five hypergraphs). More generally, we prove this for coloring and even list coloring, and also generalize this further to when $H$ is a hypergraph with small codegrees (for which high girth designs is a specific instance). Indeed, the coloring version of our result even yields an almost partition of $K_n^r$ into approximate high girth $(n,q,r)$-Steiner systems. Our main results also imply the existence of a perfect matching in a bipartite hypergraph where the parts have slightly unbalanced degrees. This has a number of applications; for example, it proves the existence of $Δ$ pairwise disjoint list colorings in the setting of Kahn's theorem; it also proves asymptotic versions of various rainbow matching results in the sparse setting (where the number of times a color appears could be much smaller than the number of colors) and even the existence of many pairwise disjoint rainbow matchings in such circumstances.
