M_{F_{2c}}(n) gap for odd n

Open case of Theorem 3 for odd $n$ · arXiv:2202.06810

arXiv Problem medium confidence— first stated 2022-04-01

Authors: Noga Alon, Anna Gujgiczer, János Körner, Aleksa Milojević, Gábor Simonyi

Status open high confidence

The question of determining $M_{F_{2c}}(n)$ for odd $n \geq 5$ remains open. The upper bound $M_{F_{2c}}(n) \leq 2^{n-2}$ is established in the source paper, but the best-known construction for odd $n$ gives only $2^{n-2} - \binom{n-2}{(n-3)/2}$, leaving a gap. A 2023 follow-up by Bai, Gao, Ma, and Wu (arXiv:2307.08266, SIAM J. Discrete Math.) studies related phase-transition problems for $M_{\mathcal{F}}(n)$ and announces a partial solution to a problem from the source paper, but this refers to Problem 3 about spanning trees with many leaves, not to the 2-connected code problem; no paper found closes the odd-$n$ gap for $M_{F_{2c}}$.

Reviewer notes. The Semantic Scholar citation list for arXiv:2202.06810 contains 17 citing papers (as of May 2026); the most topically adjacent is arXiv:2307.08266 (Bai–Gao–Ma–Wu, SIAM JDM 2024), whose 'partial solution to a recent problem posed by Alon et al.' addresses Problem 3 (spanning-tree leaf sequences), not the 2-connected code problem. Alon's 'Connectivity graph-codes' (arXiv:2308.07653, Random Struct. Algorithms 2024) and Versteegen's 'Upper Bounds for Linear Graph Codes' (arXiv:2310.19891) were identified as citing papers but do not appear to address $M_{F_{2c}}$ for odd $n$ specifically. No follow-up resolving the odd-$n$ gap was found.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Determine $M_{F_{2c}}(n)$ for odd $n \geq 5$. The upper bound $M_{F_{2c}}(n) \leq 2^{n-2}$ holds for all $n$, but the best construction for odd $n$ yields only $2^{n-2} - \binom{n-2}{(n-3)/2}$ graphs.

Context

Theorem 3 establishes $M_{F_{2c}}(n) = 2^{n-2}$ for all even $n$ via matching upper and lower bounds. For odd $n$ the upper bound still holds, but the construction from the even case fails; the best the authors could achieve gives $2^{n-2} - \binom{n-2}{(n-3)/2}$, leaving a gap. For $n = 3$ the upper bound is attained (a triangle and the empty graph), but no general matching construction is known.

Notes. Stated as Remark 2 without a formal Problem/Conjecture environment; the authors do not explicitly conjecture the true value for odd $n$ but clearly identify it as an open case.

Source paper

Structured Codes of Graphs
Noga Alon, Anna Gujgiczer, János Körner, Aleksa Milojević, Gábor Simonyi · 2022-04-01
https://arxiv.org/abs/2202.06810 PDF source