betaFeedback

WorksMathematics

Hypergraph Hajnal-Szemerédi

Abstract

A seminal result of Hajnal and Szemerédi from 1970 asserts that every graph on nn vertices with q  ∣  nq\;|\;n and minimum degree at least (1−1q)n\Big(1-\frac{1}{q}\Big)n admits a KqK_q-factor (a collection of vertex-disjoint copies of KqK_q spanning all vertices). There has been sustained interest in extending this result to hypergraph KqrK_q^r-factors. For general qq and rr, Lu and Székely in 2007 showed that every large enough, rr-graph GG with q∣v(G)q\mid v(G) and δr−1(G)≥(1−cqr−1)v(G)δ_{r-1}(G) \ge \left(1- \frac{c}{q^{r-1}}\right)v(G) admits a KqrK_q^r-factor (where cc is a constant depending on rr but not qq), 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 δr−1(G)≥(1−c⋅log⁡qqr−1)v(G)δ_{r-1}(G) \ge \left(1 - \frac{c \cdot \log q}{q^{r-1}} \right)v(G) is necessary. Surprisingly, our main result shows that the order of this upper bound is not correct and, in fact, the codegree KqrK_q^r-factor threshold is much closer to this codegree Turán theory bound. In particular, we show that δr−1(G)≥(1−c⋅log⁡1−1/(r−1)qqr−1)v(G)δ_{r-1}(G) \ge \left( 1-c\cdot \frac{\log^{1-1/(r-1)}q}{q^{r-1}}\right)v(G) suffices for the existence of a KqrK_q^r-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.

Paper details

vlnc:W_h7my36ye
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…