The odd-cycle naive-dimension conjecture
Fix an odd cycle , with , and let denote the minimum dimension of an isometric embedding of into an abelian Cayley graph. Encode the edge-generator dependencies by the binary code
The code contains the all-ones vector, and for every cyclic interval isometry requires
Odd-cycle naive-dimension conjecture. The cyclic interval lemma holds for every odd ; consequently,
for every odd cycle. The claim is proved in the paper for every odd and for any further odd for which the cyclic interval lemma holds; the general case remains open.
References
- Fokam Souop Rigobert and Bitjoka Laurent, “Dimension and Order Bounds for Isometric Embeddings of Graphs into Abelian Cayley Graphs, and the Abelian Dividend”, arXiv:2607.07939 (2026).
Progress summary
A July 2026 preprint verifies the conjecture only for small odd cycles, while an unverified submission claims a proof for every odd cycle.
The conjecture predicts that the cyclic-interval condition always holds and therefore that for every odd . Fokam Souop and Bitjoka formulate the reduction in their 2026 preprint.
Known results; July 2026 preprint
- Fokam Souop and Bitjoka (2026) prove the dimension formula in the finite checked range, reported as odd .
- For any further odd satisfying the cyclic-interval lemma, their reduction gives .
- The preprint does not prove the lemma for all odd and reports no counterexample or independent verification.
Community submission (unverified)
A submitted proof argues, via averaging over cyclic intervals of lengths and for , that every nonempty proper subset is strictly closer to some interval than to the trivial alternatives; it then claims the full formula . The argument has not been independently verified.
Current status (as of August 2026): The formula is established in the finite checked range and conditionally beyond it when the cyclic-interval lemma holds; the all-odd case remains open because the submitted proof is unverified.
Sources
Solutions 1
This solution needs a summarySee full solution
Proof of the cyclic-interval conjecture and the exact binary dimension of every odd cycle
Fokam Souop and Bitjoka, arXiv:2607.07939v1, Lemma 3 and Conjecture 1, ask whether, for every odd integer and every nonempty proper subset , there exists a cyclic interval satisfying
They prove this in one special geometric regime and verify the remaining cases only for . We prove (1) for every odd , and then derive the full conjectured binary embedding dimension.
An averaging identity for cyclic intervals
Write
For and , define the cyclic interval
Each element of belongs to exactly of these intervals. Therefore
The necessary interval length depends only on the parity of .
Case 1: is odd. Take . From (4), the average intersection size is
where strictness follows from . Since intersection sizes are integers, some interval satisfies
Consequently,
Case 2: is even. Take . This time (4) gives
since . Thus some interval satisfies
It follows that
Together, (7) and (10) prove (1) for every nonempty proper and every odd .
Consequence: the exact dimension of every odd cycle
Let have cyclically ordered vertices , and suppose it embeds isometrically into a binary Cayley graph on . For each edge define its generator
Because the edges close to a cycle,
Introduce the dependency space
Equation (12) states that the all-ones vector belongs to . If the generators had rank at most , then , so would contain the indicator of some nonempty proper subset .
Choose the cyclic interval supplied by (1). If its endpoints on are and , then
Every is an allowed generator of the host Cayley graph. Hence (14) exhibits a host walk from to of length at most . But (1) gives
contradicting isometry. Therefore
For completeness, this lower bound is attained. In take
Their only nonzero binary dependency uses all generators. Set
For an arc , the only generator subsets representing its endpoint difference are and its complement. Because repeated generators cancel in characteristic , the host distance is exactly
Thus this embedding is isometric, proving the full conjecture: