Why cycle-space rank does not give the color bound

---

This page preserves an earlier research route and its local standing. The completed threshold proof is in the solution note.

The examples below obstruct a binary cycle-space method while leaving the threshold conjecture open.

Let $D$ be the binary vertex-edge incidence matrix of $G$, and let $P:\mathbb F_2^{E(G)}\to\mathbb F_2^r$ send an edge to the basis vector of its color. Write $Z_1(G)=\ker D$ for the binary cycle space.

Nonvanishing and rank do not encode the rainbow condition

Since $\mathbf1^{\mathsf T}P=\mathbf1^{\mathsf T}$, every odd cycle vector $z$ satisfies $\mathbf1^{\mathsf T}Pz=1$, for every coloring. The C7-rainbow condition requires the much stronger assertion $|\operatorname{supp}(Pz)|=7$, not merely $Pz\ne0$.

Moreover, if $c(G)$ is the number of connected components,

$$\dim(\ker P\cap Z_1(G)) =\dim\ker\begin{pmatrix}D\\P\end{pmatrix} \ge e-r-n+c(G).$$

At quadratic edge and color counts near the conjectured extremum, a quadratic-dimensional color-even cycle space is therefore unavoidable.

A concrete example where seven-cycles span everything

Use the three-branch graph, with its aligned coloring of the three complete bipartite wings. It is chordal: first eliminate the vertices in $U_i$, whose neighborhoods $A_i$ are cliques, and then eliminate the wing cliques. Hence its cycle space is generated by triangles; this also follows by repeatedly splitting a cycle along a chord.

Every triangle is contained in a clique of order at least seven for sufficiently large $n$. Triangles through a tip lie in $\{u\}\cup A_i$, and all other triangles lie in $C\cup A_i$. In any $K_m$ with $m\ge7$, seven-cycles span its entire cycle space. Here is a direct verification. Swapping consecutive interior vertices in a seven-cycle gives, as the binary difference, any prescribed four-cycle:

$$(a,b,c,d,e,f,g,a)+(a,c,b,d,e,f,g,a) =\{ab,bd,dc,ca\}.$$

Four-cycles span the even-edge-cardinality subspace of the cycle space. For example, using the standard triangle basis through a fixed vertex, differences of triangles whose other endpoint pairs share a vertex are four-cycles; these connect the entire triangle basis. Adding any odd seven-cycle supplies the remaining one-dimensional quotient. Thus the seven-cycles of the three-branch graph span all of $Z_1(G)$.

Nevertheless, the color map has a large kernel on that space. Put $a=|A_i|$, $u=|U_i|$, and identify the three wings coordinatewise. All non-wing colors are unique, so a vector in $\ker P$ is supported on the wings. Such a vector is Eulerian exactly when each branch restriction lies in $Z_1(K_{a,u})$, and the color condition says that the three restrictions sum to zero. Consequently

$$\ker P\cap Z_1(G)\cong Z_1(K_{a,u})^2, \qquad \dim=2(a-1)(u-1).$$

For the recorded parameters this is $0.002n^2-0.22n+2$. Its minimum nonzero support size is exactly eight: at least two branch restrictions are nonzero, each has at least four edges, and two corresponding four-cycles attain eight.

Scope of the obstruction

Full span by seven-cycles does not imply that color identification is injective on that span. Even adding minimum support eight for the color-even cycle code does not remove its quadratic dimension. This rules out the direct rank/injectivity argument investigated here; it does not rule out every possible nonlinear use of cycle spaces or coding theory.