WorksMathematics
Hypergraph Hajnal-Szemerédi
Abstract
A seminal result of Hajnal and Szemerédi from 1970 asserts that every graph on vertices with and minimum degree at least admits a -factor (a collection of vertex-disjoint copies of spanning all vertices). There has been sustained interest in extending this result to hypergraph -factors. For general and , Lu and Székely in 2007 showed that every large enough, -graph with and admits a -factor (where is a constant depending on but not ), and there have been various subsequent improvements to the constant (but not the order) of this bound over the ensuing decades. Meanwhile, results from codegree Turán theory show that is necessary. Surprisingly, our main result shows that the order of this upper bound is not correct and, in fact, the codegree -factor threshold is much closer to this codegree Turán theory bound. In particular, we show that suffices for the existence of a -factor. Our key contribution is showing the same is true for the fractional threshold. Inspired by the first and fourth author's recent proof of the Nash-Williams' Conjecture, we accomplish this by combining a linear programming framework with ideas from discharging. Additionally, we establish a technical result about finding large independent sets in sparse, non-uniform hypergraphs, which may be of independent interest.