Skip to content
Preprint

Cyclic Incidence Orderings of Complete Graphs and 3-Uniform Hypergraphs

Sep 2026 · 0 citations · 9 references
Mathematics

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\leq 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 $3\nmid 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.

View source

Similar papers

Preprint Oct 2026

A Fan-Type Theorem for Hamiltonian Berge Cycles in 3-Uniform Hypergraphs

Let $H$ be a simple $3$-uniform hypergraph on $n\ge7$ vertices, and put $\tau_n=\binom{\lfloor(n-1)/2\rfloor}{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 $\tau_n+1$, and every pair of codegree one...

Ai-Lian Chen, Yan-Qiang Liu · 0 citations
Preprint Oct 2026

Off-diagonal Ramsey numbers for 3-uniform tight hypergraph cycles

Let $C^{(3)}_n$ be the $3$-uniform tight cycle on $n$ vertices, that is, the $3$-uniform hypergraph on a cyclically ordered set of $n$ vertices whose edges are precisely the triples of consecutive vertices in the given cyclic order. We asymptotically determine the off-diagonal Ramsey numbers of $3$-uniform tight cycles...

Eng Keat Hng · 0 citations
Preprint Nov 2026

Circular flows and bisections of random regular graphs

For every fixed odd $d\ge5$, we prove that the circular flow number of a uniformly random simple $d$-regular graph is asymptotically almost surely less than $2+4/(d-1)-\varepsilon_d$ for an explicit constant $\varepsilon_d>0$. At degree five the upper bound is $3-1/24006$. At degree seven it is $21/8$, answering a ques...

A. Jafari · 0 citations
Preprint Oct 2026

A uniform double-factorial construction for consecutive-pattern packings

For every overlap $m\geq 3$ and every pattern length $K\geq 2m+1$, we construct an explicit permutation $p\in\mathfrak{S}_K$ such that the number of permutations containing $j$ prescribed occurrences of $p$, with successive starts separated by $K-m$, is $(2j-1)!!$ for every $j\geq 1$. Additional occurrences are permitt...

Zoltán Nagy · 0 citations
Preprint Nov 2026

Every $k$-Quasi-Planar Graph Has Linearly Many Edges

For every fixed integer $k\ge2$, we prove that every simple graph on $n$ vertices drawn in the plane with no $k$ pairwise crossing edges has at most $C_kn$ edges, where $C_k$ depends only on $k$. We allow any finite number of proper crossings between two edges, including edges with a common endpoint. For $n\ge3$, remov...

A. Sadhu · 1 citation
Preprint Oct 2026

Generating cyclic pivot Gray codes for well-ordered $k$-degenerate graphs in constant amortized time

A graph $G$ is $k$-degenerate if there exists an ordering $v_1, v_2, \dots, v_n$ of its vertices such that each vertex $v_i$ has at most $k$ neighbors $v_j$ in $G$ with $j<i$. A well-ordered $k$-degenerate graph is a labeled graph on the vertex set $\{1, 2, \dots, n\}$ in which every vertex $i$ has at most $k$ neighbor...

Lei Dong, Dennis Wong, Bowie Liu et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.