On the Hypergraph Nash-Williams' Conjecture

Abstract

In 2014, Keevash proved the existence of $(n,q,r)$-Steiner systems (equivalently $K_q^r$-decompositions of $K_n^r$) for all large enough $n$ satisfying the necessary divisibility conditions. In 2021, Glock, Kühn, and Osthus proposed a generalization of this result. Namely they conjectured a hypergraph version of Nash-Williams' Conjecture positing that if a $K_q^r$-divisible $r$-graph $G$ on $n$ vertices has minimum $(r-1)$-degree (denoted $\hat{I}´(G)$ hereafter) at least $\left(1-\hat{I}{˜}_r\left(\frac{1}{q^{r-1}}\right)\right)\cdot n$, then $G$ admits a $K_q^r$-decomposition. The best known progress on this conjecture dates to the second proof of the Existence Conjecture by Glock, Kühn, Lo, and Osthus wherein they showed that $\hat{I}´(G)\ge \left(1-\frac{c}{q^{2r}}\right)\cdot n$ suffices for large enough $n$, where $c$ is a constant depending on $r$ but not $q$. As for the fractional relaxation, the best known bound is due to Delcourt, Lesgourgues, and the second author, who proved that $\hat{I}´(G)\ge \left(1-\frac{c}{q^{r-1+o(1)}}\right)\cdot n$ guarantees a $K_q^r$-fractional decomposition. We prove that for every integer $r\ge 2$, there exists a real $c>0$ such that if a $K_q^r$-divisible $r$-graph $G$ satisfies $\hat{I}´(G)\ge \max \left\{\hat{I}{´}_{K_q^r}^{\ast }+\epsilon ,1-\frac{c}{\left(\genfrac{}{}{0ex}{}{q}{r-1}\right)}\right\}\cdot n$, then $G$ admits a $K_q^r$-decomposition for all large enough $n$, where $\hat{I}{´}_{K_q^r}^{\ast }$ denotes the fractional $K_q^r$-decomposition threshold. Combined with the fractional result above, this proves that $\left(1-\frac{c}{q^{r-1+o(1)}}\right)\cdot n$ suffices for the Hypergraph Nash-Williams' Conjecture, approximately confirming the correct order of $q$. Our proof uses the newly developed method of refined absorption; we also develop a non-uniform Turán theory to prove the existence of many embeddings of absorbers which may be of independent interest.

35 pages