On the characterization of some algebraically defined bipartite graphs of girth eight*

NEW

Problem: For a field $F$ and $f_2,f_3\in F[x,y]$, let $\Gamma_F(f_2,f_3)$ be the simple bipartite graph with parts $P=L=F^3$, where

The conjecture states that, for $F=\mathbb F_q$ with $q$ odd or for algebraically closed $F$ of characteristic $0$, every $\Gamma_F(f_2,f_3)$ of girth at least $8$ is isomorphic to $\Gamma_3(F)=\Gamma_F(xy,x^2y)$. The paper sometimes uses $(xy,xy^2)$; these two standard graphs are isomorphic by interchanging the two bipartition classes.

Result: The conjecture is false already over $\mathbb F_3$. Work in $\mathbb F_3$, and set

Writing $A(x,y)=(f_2(x,y),f_3(x,y))$, its values are

A 4-cycle would require, for some $a\ne b$, that $A(a,y)-A(b,y)$ take the same value at two distinct $y$’s. But for $\{a,b\}=\{0,1\},\{0,2\},\{1,2\}$, these difference lists are respectively

all injective. Hence there is no 4-cycle.

A 6-cycle would give pairwise distinct $x_1,x_2,x_3$ and $y_1,y_2,y_3$ with

Up to cyclic rotation the $x$-sequence is $012$ or $021$. Direct evaluation gives:

No entry is $0$. Thus there is no 6-cycle. The graph has the explicit 8-cycle

so its girth is exactly $8$.

It remains to show it is not isomorphic to $\Gamma_3(\mathbb F_3)$. Let $\omega$ be a primitive cube root of unity. For each character $c=(u,v)\in\mathbb F_3^2$, form

Fourier decomposition over the additive group $\mathbb F_3^2$ gives the adjacency spectrum from the singular values of these $3\times3$ matrices. Exact calculation gives, for the counterexample,

whereas for $\Gamma_3(\mathbb F_3)$,

The characteristic polynomials differ, so the graphs are not isomorphic.

Thus the literal conjecture fails. The failure is a small-field exception: any repaired statement must at least exclude this $\mathbb F_3$ phenomenon or impose a stronger “stable over extensions” hypothesis.

Citation: The conjecture and graph definition are from Xu–Cheng–Tang, “On the characterization of some algebraically defined bipartite graphs of girth eight,” arXiv:1912.04592. The counterexample above is the resolution given here.