On the Hypergraph Nash-Williams' Conjecture
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918230480650240 |
|---|---|
| author | Henderson, Cicely Postle, Luke |
| author_facet | Henderson, Cicely Postle, Luke |
| contents | 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 $δ(G)$ hereafter) at least $\left(1-Θ_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 $δ(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 $δ(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 $δ(G)\ge \max\left\{ δ_{K_q^r}^* + \varepsilon,~~1 -\frac{c}{\binom{q}{r-1}} \right\} \cdot n$, then $G$ admits a $K_q^r$-decomposition for all large enough $n$, where $δ_{K_q^r}^*$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_04071 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Hypergraph Nash-Williams' Conjecture Henderson, Cicely Postle, Luke Combinatorics 05B05, 05B07, 05B40, 05C35, 05C65 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 $δ(G)$ hereafter) at least $\left(1-Θ_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 $δ(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 $δ(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 $δ(G)\ge \max\left\{ δ_{K_q^r}^* + \varepsilon,~~1 -\frac{c}{\binom{q}{r-1}} \right\} \cdot n$, then $G$ admits a $K_q^r$-decomposition for all large enough $n$, where $δ_{K_q^r}^*$ 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. |
| title | On the Hypergraph Nash-Williams' Conjecture |
| topic | Combinatorics 05B05, 05B07, 05B40, 05C35, 05C65 |
| url | https://arxiv.org/abs/2512.04071 |