A Fan-Type Theorem for Hamiltonian Berge Cycles in 3-Uniform Hypergraphs
Abstract
Let H be a simple $3$-uniform hypergraph on n≥7 vertices, and put τn=binom⌊(n−1)/2⌋2. We prove that H has a Hamiltonian Berge cycle if its $2$-shadow is $2$-connected, every pair at Berge distance two has an endpoint of hypergraph degree at least τn+1, and every pair of codegree one has both endpoints above τn. The distance-two threshold is sharp, and the order range cannot be extended to n=4,5,6. The proof separates two structural arguments. A low-degree endpoint of an extremal longest Berge path forces Hamiltonicity, independently of the order and the degree threshold. For high-degree endpoints, injective charging and its equality cases force pairs of codegree one that permit further rotations. The cases n=7,8 are settled by exhaustive verification, with a completeness proof and a second implementation using direct vertex--hyperedge cycle search. Keywords: Hamiltonian Berge cycle; Fan-type condition; 3-uniform hypergraph; longest-path rotation; exhaustive verification.
Related
- A Chvátal-type codegree condition for Hamiltonian cycles in k-uniform hypergraphs
- Spectral extremal hypergraphs without long Berge cycles
- Rainbow Berge Hamiltonicity in edge-colored random k-uniform hypergraphs
- Saturation in three-uniform Berge hypergraphs: the five-star spectrum and the K4 saturation number
- Extremal 3-uniform hypergraphs without generalized 4-cycles
BibTeX
@misc{chen2026fantype,
title = {{A Fan-Type Theorem for Hamiltonian Berge Cycles in 3-Uniform Hypergraphs}},
author = {Ailian Chen and Yanqiang Liu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41577},
eprint = {2610.41577},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41577},
}
RIS
TY - UNPB
TI - A Fan-Type Theorem for Hamiltonian Berge Cycles in 3-Uniform Hypergraphs
AU - Ailian Chen
AU - Yanqiang Liu
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41577
UR - https://arxiv.org/abs/2610.41577
AB - Let H be a simple $3$-uniform hypergraph on n≥7 vertices, and put τ_n=binom⌊(n−1)/2⌋2. We prove that H has a Hamiltonian Berge cycle if its $2$-shadow is $2$-connected, every pair at Berge distance two has an endpoint of hypergraph degree at least τ_n+1, and every pair of codegree one has both endpoints above τ_n. The distance-two threshold is sharp, and the order range cannot be extended to n=4,5,6. The proof separates two structural arguments. A low-degree endpoint of an extremal longest Berge path forces Hamiltonicity, independently of the order and the degree threshold. For high-degree endpoints, injective charging and its equality cases force pairs of codegree one that permit further rotations. The cases n=7,8 are settled by exhaustive verification, with a completeness proof and a second implementation using direct vertex--hyperedge cycle search. Keywords: Hamiltonian Berge cycle; Fan-type condition; 3-uniform hypergraph; longest-path rotation; exhaustive verification.
ER -