A NOTE ON GRAPHS WITH A PRESCRIBED ADJACENCY PROPERTY

NEW

Problem: Reconstructed conjecture (Remark 2): Let $q\equiv1\pmod4$ be a prime power, $k\ge1$, and let $G_q$ be the Paley graph on $\mathbb F_q$. If

then $G_q\notin \mathcal G(1,2,k)$; i.e. there exist distinct vertices $a,b,c$ such that fewer than $k$ vertices are adjacent to $a$ and nonadjacent to both $b,c$.

This is exactly the statement following the authors’ computer verification for $q\le1009$.

Result: The conjecture is false. Take

Then

since $27^2<754$. But $G_{3125}\in\mathcal G(1,2,377)$.

Proof. Let $F=\mathbb F_{3125}$ and let $\eta$ be its quadratic character. Since $q\equiv1\pmod4$, $\eta(-1)=1$. By translation, it suffices to count, for distinct $0,b,c$,

Put

For the nonsingular elliptic curve

we have $\#E_{b,c}(F)=q+1+S$. Hasse gives

so $S\ge -111$.

Expanding the indicator product gives

where

A direct check with signs $\pm1$ gives $R\in\{0,4,8\}$. Hence

so $N(b,c)\ge376$.

If $N(b,c)=376$, then

so $S=R-118$. Since $S\ge-111$ and $R\in\{0,4,8\}$, necessarily $R=8$ and $S=-110$. Then $E_{b,c}$ would have trace

But Waterhouse’s classification of elliptic-curve traces says that over $\mathbb F_{p^r}$, with $p>3$ and $r$ odd, the only trace divisible by $p$ that can occur for a supersingular elliptic curve is $0$; ordinary traces are not divisible by $p$. Here $p=5$, $r=5$, and $110\ne0$ is divisible by $5$, impossible.

Thus $N(b,c)\ne376$, so $N(b,c)\ge377$ for all distinct $b,c$. Therefore $G_{3125}\in\mathcal G(1,2,377)$, contradicting the conjecture.

Citation: Uses the conjecture from Ananchuen–Caccetta, “A note on graphs with a prescribed adjacency property,” Bull. Austral. Math. Soc. 50 (1994), Remark 2. The trace obstruction uses W. C. Waterhouse, “Abelian varieties over finite fields,” Ann. Sci. École Norm. Sup. 2 (1969), 521–560.