Odd-Cycle Span Defect: A Polynomial Lower Bound and a Square-Root Upper Bound

Abstract

For a graph $G$, let $\ddot{I}ˆ(G)=\max \{\ddot{I}‡(G[V(C)]):C$ is an odd cycle of $G\}$, with $\ddot{I}ˆ(G)=0$ when $G$ is bipartite. For positive integers $N$, set $F(N)=\max \{\ddot{I}‡(G)-\ddot{I}ˆ(G):|V(G)|\le N\}$. The function $F$ measures the finite-order additive gap arising from an open problem of Erdos and Hajnal. We prove $N^{1/6-o(1)}\le F(N)<\sqrt{6N}$. The lower bound raises the finite-order scale supplied by the Cameron-Clow path-colour construction from $\log N/\log \log N$ to a fixed power of $N$. Its proof constructs a palette-code graph from a binary covering code $\mathcal{C}\subseteq \{0,1{\}}^p$ and establishes the exact identities $\ddot{I}‡(G)=2p+\ell -\ddot{I}(\mathcal{C})$ and $\ddot{I}ˆ(G)=2p$. Near-middle Hamming coverings yield the exponent $1/6$. The upper bound combines Polavarapu's connectivity theorem, the Chvatal-Erdos Hamiltonicity theorem, and maximum-independent-set stripping.