Cyclic Incidence Orderings of Complete Graphs and 3-Uniform Hypergraphs
Abstract
We study cyclic orderings of all edges of a complete k-uniform hypergraph on n vertices in which the binary incidence sequences of the vertices are cyclic shifts of a common word. The shifts are chosen independently, with no prescribed action on the vertices. For 2≤ k<n, coprimality gcd(n,k)=1 is known to suffice even when consecutive edges must differ by a single vertex exchange. We recall a short orbit construction and prove the converse for the first two nontrivial uniformities without any adjacency requirement. For k=2, an ordering exists exactly when n=2 or n is odd; for k=3, exactly when n=3 or 3nmid n. The necessity proofs use reflected convolution identities and pair-intersection counts to constrain the vertex shifts to a torsion coset. For triples, multiplicity-preserving dilation and conditional prime-power capacity bounds complete the argument.
Related
- The maximum spectral radius of uniform hypergraphs whose shadow excludes a complete or complete bipartite minor
- Erdős-Sós via random cyclic orderings
- Phase transition of random non-uniform hypergraphs
- Irregular Triads in 3-Uniform Hypergraphs
- Towards the Erdős matching conjecture for 4‐uniform hypergraphs: Stability and applications
BibTeX
@misc{zhou2026cyclic,
title = {{Cyclic Incidence Orderings of Complete Graphs and 3-Uniform Hypergraphs}},
author = {Junyu Zhou},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06724},
eprint = {2609.06724},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06724},
}
RIS
TY - UNPB
TI - Cyclic Incidence Orderings of Complete Graphs and 3-Uniform Hypergraphs
AU - Junyu Zhou
PY - 2026
DA - 2026/09/06
PB - arXiv
DO - 10.48550/arxiv.2609.06724
UR - https://arxiv.org/abs/2609.06724
AB - We study cyclic orderings of all edges of a complete k-uniform hypergraph on n vertices in which the binary incidence sequences of the vertices are cyclic shifts of a common word. The shifts are chosen independently, with no prescribed action on the vertices. For 2≤ k<n, coprimality gcd(n,k)=1 is known to suffice even when consecutive edges must differ by a single vertex exchange. We recall a short orbit construction and prove the converse for the first two nontrivial uniformities without any adjacency requirement. For k=2, an ordering exists exactly when n=2 or n is odd; for k=3, exactly when n=3 or 3nmid n. The necessity proofs use reflected convolution identities and pair-intersection counts to constrain the vertex shifts to a torsion coset. For triples, multiplicity-preserving dilation and conditional prime-power capacity bounds complete the argument.
ER -