Finding an almost perfect matching in a hypergraph avoiding forbidden submatchings

Abstract

In 1973, Erdős conjectured the existence of high girth ‐Steiner systems. Recently, Glock, Kühn, Lo, and Osthus and independently Bohman and Warnke proved the approximate version of Erdős' conjecture. Recently, 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 ‐Steiner systems. We prove the approximate version of their conjecture. This result follows from our general main results that concern finding perfect or almost perfect matchings in a hypergraph avoiding a given set of submatchings (which we view as a hypergraph where ). 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 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 into approximate high girth ‐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 other applications; for example, it proves the existence of pairwise disjoint list colorings in the setting of Kahn's theorem for list coloring the edges of a hypergraph; 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.