Exact supported co-degree bounds for Hamilton cycles
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914188893356032 |
|---|---|
| author | Letzter, Shoham Ranganathan, Arjun |
| author_facet | Letzter, Shoham Ranganathan, Arjun |
| contents | For any $k\ge 3$ and $\ell \in [k-1]$ such that $(k,\ell) \ne (3,1)$, we show that any sufficiently large $k$-graph $G$ must contain a Hamilton $\ell$-cycle provided that it has no isolated vertices and every set of $k-1$ vertices contained in an edge is contained in at least $\left(1 - \frac{1}{\lfloor{\frac{k}{k-\ell}\rfloor}(k-\ell)}\right)n - (k - 3)$ edges. We also show that this bound is tight for infinitely many values of $k$ and $\ell$ and is off by at most $1$ for all others, and is hence essentially optimal. This improves an asymptotic version of this result due to Mycroft and Zárate-Guerén, and the case $\ell = k-1$ completely resolves a conjecture of Illingworth, Lang, Müyesser, Parczyk and Sgueglia.
These results support the utility of $\textit{minimum}$ $\textit{supported}$ $\textit{co-degree}$ conditions in a $k$-graph, a recently introduced variant of the standard notion of minimum co-degree applicable to $k$-graphs with non-trivial strong independent sets. Our proof techniques involve a novel blow-up tiling framework introduced by Lang, avoiding traditional approaches using the regularity and blow-up lemmas. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_07751 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Exact supported co-degree bounds for Hamilton cycles Letzter, Shoham Ranganathan, Arjun Combinatorics For any $k\ge 3$ and $\ell \in [k-1]$ such that $(k,\ell) \ne (3,1)$, we show that any sufficiently large $k$-graph $G$ must contain a Hamilton $\ell$-cycle provided that it has no isolated vertices and every set of $k-1$ vertices contained in an edge is contained in at least $\left(1 - \frac{1}{\lfloor{\frac{k}{k-\ell}\rfloor}(k-\ell)}\right)n - (k - 3)$ edges. We also show that this bound is tight for infinitely many values of $k$ and $\ell$ and is off by at most $1$ for all others, and is hence essentially optimal. This improves an asymptotic version of this result due to Mycroft and Zárate-Guerén, and the case $\ell = k-1$ completely resolves a conjecture of Illingworth, Lang, Müyesser, Parczyk and Sgueglia. These results support the utility of $\textit{minimum}$ $\textit{supported}$ $\textit{co-degree}$ conditions in a $k$-graph, a recently introduced variant of the standard notion of minimum co-degree applicable to $k$-graphs with non-trivial strong independent sets. Our proof techniques involve a novel blow-up tiling framework introduced by Lang, avoiding traditional approaches using the regularity and blow-up lemmas. |
| title | Exact supported co-degree bounds for Hamilton cycles |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.07751 |