Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 46 min ago
PreprintarXiv licencearXiv

Large tight components and Dirac thresholds for tight Hamilton cycles

  • Hao Lin
  • Guanghui Wang
  • Jiande Zhang
  • Wenling Zhou
Open at sourcePDFDOICite

Abstract

For every odd integer r≥1, let qr=1−2−rbinom r(r−1)/2. We show that, for every odd r≥3 and sufficiently large n, every n-vertex r-uniform hypergraph with at least qrbinom nr edges contains a tight component with at least (1/2−o(1))binom nr edges. This confirms a conjecture posed by Lang and Sanhueza-Matamala in 2024. As an application, for every odd r≥1 and every integer k≥⌈ r(3−2qr)⌉, we prove that the asymptotic minimum (k−r)-degree threshold for a tight Hamilton cycle in a k-uniform hypergraph is qr, which settles, in this range, another conjecture of Lang and Sanhueza-Matamala in 2022 stating that the lower-bound construction due to Han and Zhao is asymptotically optimal. Our proof combines an isoperimetric inequality for Johnson graphs with a Kruskal-Katona-type theorem, which is of independent interest.

Related

  1. Prescribed Color Patterns in Tight Hamilton Cycles and Spanning Trees
    Lirong Deng
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. On Hamilton cycles in quasiprimitive graphs of order 2pq
    Hao Yu, Tianlei Zhou
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  3. Alternating Hamilton Paths and Cycles in Poset Products
    Yuxian Dong, Jianxi Mao
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv
  4. On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof
    Chengli Li, Feng Liu
    The Electronic Journal of CombinatoricsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref
  5. Tournaments with many Hamilton cycles
    N. C. Wormald
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{lin2026large,
  title = {{Large tight components and Dirac thresholds for tight Hamilton cycles}},
  author = {Hao Lin and Guanghui Wang and Jiande Zhang and Wenling Zhou},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.38560},
  eprint = {2610.38560},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.38560},
}
RIS
TY  - UNPB
TI  - Large tight components and Dirac thresholds for tight Hamilton cycles
AU  - Hao Lin
AU  - Guanghui Wang
AU  - Jiande Zhang
AU  - Wenling Zhou
PY  - 2026
DA  - 2026/10/28
PB  - arXiv
DO  - 10.48550/arxiv.2610.38560
UR  - https://arxiv.org/abs/2610.38560
AB  - For every odd integer r≥1, let q_r=1−2^−rbinom r(r−1)/2. We show that, for every odd r≥3 and sufficiently large n, every n-vertex r-uniform hypergraph with at least q_rbinom nr edges contains a tight component with at least (1/2−o(1))binom nr edges. This confirms a conjecture posed by Lang and Sanhueza-Matamala in 2024. As an application, for every odd r≥1 and every integer k≥⌈ r(3−2q_r)⌉, we prove that the asymptotic minimum (k−r)-degree threshold for a tight Hamilton cycle in a k-uniform hypergraph is q_r, which settles, in this range, another conjecture of Lang and Sanhueza-Matamala in 2022 stating that the lower-bound construction due to Han and Zhao is asymptotically optimal. Our proof combines an isoperimetric inequality for Johnson graphs with a Kruskal-Katona-type theorem, which is of independent interest.
ER  -