An infinite sequence of triangle-free K_{2,7}-free graphs of diameter 2

Recall that a Moore graph (of diameter 2) is a regular graph of girth ${5}$ and diameter ${2}$ . Equivalently, it is a triangle-free graph such that any two nonadjacent vertices have a unique common neighbour. There are famously few Moore graphs: only the 5-cycle of degree 2, the Petersen graph of degree 3, and the Hoffman–Singleton graph of degree 7, and possibly a graph (or even several graphs) of degree ${57}$ and order ${3250}$ (the “missing Moore graph”). This is the Hoffman–Singleton theorem.

The Hoffman–Singleton theorem being too mysterious, it is tempting to try to find a weakening of the definition of a Moore graph that allows a few more graphs but still finitely many. One hopes that the “finitely many” part would have some more direct combinatorial proof (as opposed to the algebraic voodoo that goes into Hoffman–Singleton). Such a conjecture was recently posed by Wood and stated in a paper of Devillers, Kamcev, McKay, O Cathain, Royle, Van de Voorde, Wanless, and Wood.

Conjecture 1 For every integer ${t \ge 2}$ there are only finitely many triangle-free ${K_{2,t}}$ -free graph with diameter ${2}$ apart from stars.

For ${t = 2}$ this is immediate from Hoffman–Singleton. The authors (Devillers, Kamcev, …) find almost ${6}$ million examples of such graphs with ${t=3}$ , but “nothing suggestive of an infinite class”. However, the following construction (which arose in conversations with Padraig O Cathain) disproves the conjecture for ${t = 7}$ .

Let ${p}$ be a prime congruent to ${11}$ mod ${12}$ . This condition ensures that ${-1}$ and ${-3}$ are quadratic nonresidues. Let ${G = \mathbf{F}_p^2}$ and let ${A = \{(x, \pm x^2) : x \in \mathbf{F}_p, x \ne 0\}}$ . Now consider the Cayley graph ${\mathrm{Cay}(G, A)}$ . Equivalently, this is the graph with vertex set $\mathbf{Z}/p\mathbf{Z} \times \mathbf{Z}/p\mathbf{Z}$ and $(x_1, y_1)$ joined to $(x_2, y_2)$ if and only if $y_1 - y_2 = \pm (x_1 - x_2)^2 \ne 0$ . We claim ${\mathrm{Cay}(G, A)}$ is triangle-free, ${K_{2,7}}$ -free, and diameter-2.

Claim 1: ${\mathrm{Cay}(G, A)}$ is triangle-free. Equivalently, ${A}$ is sum-free.

Proof: We must check that there do not exist nonzero ${x, y, z}$ such that ${(x, \pm x^2) + (y, \pm y^2) + (z, \pm z^2) = 0}$ . Equivalently, we must check that

$\displaystyle (x+y)^2 \pm x^2 \pm y^2 = 0$

implies ${xy(x+y) = 0}$ . There are four cases, depending on the two signs:

${(-, -)}$ : We get ${2xy = 0}$ .

${(-, +)}$ : We get get ${2(x+y)y = 0}$ .

${(+, -)}$ : We get ${2(x+y)x = 0}$ .

${(+, +)}$ : We get ${x^2 + xy + y^2 = 0}$ . Since polynomial ${X^2 + X + 1}$ has discriminant ${-3}$ , which is a quadratic nonresidue, it follows that ${x = y = 0}$ .

Claim 2: ${\mathrm{Cay}(G, A)}$ is ${K_{2,7}}$ -free and diameter- ${2}$ . In fact, we have ${2 \le 1_A * 1_A(g) \le 6}$ for every nonzero ${g \notin A}$ .

Here ${1_A * 1_A(g)}$ is the number of solutions to ${a_1 + a_2 = g}$ with ${a_1, a_2 \in A}$ . It is an exercise to check that the first statement follows from the second, so we just prove the second.

Proof: Let ${g = (z, w)}$ be a nonzero point not in ${A}$ . First assume ${z \ne 0}$ . The value of ${1_A*1_A(g)}$ is the number of quadruples ${(x, y, \epsilon_1, \epsilon_2)}$ with ${x, y \in \mathbf{F}_p}$ nonzero and ${\epsilon_1, \epsilon_2 = \pm 1}$ such that

$\displaystyle x + y = z, \qquad \epsilon_1 x^2 + \epsilon_2 y^2 = w.$

For fixed ${z, w, \epsilon_1, \epsilon_2}$ is equivalent to count ${x \ne 0, z}$ such that

$\displaystyle \epsilon_1 x^2 + \epsilon_2 (x-z)^2 = w.$

If the signs are equal then this is a nontrivial quadratic equation, so there are at most ${2}$ solutions. If the signs are different then we get a linear equation

$\displaystyle 2xz - z^2 = \epsilon_1 w,$

which has a unique solution. If that solution is ${0}$ or ${z}$ then we get ${w = \pm z^2}$ , contrary to the assumption that ${g \notin A}$ .

Now assume ${z = 0}$ and ${w}$ is nonzero. Then ${1_A * 1_A(g)}$ is the number of triples ${(x, \epsilon_1, \epsilon_2)}$ with ${x}$ nonzero such that ${(\epsilon_1 + \epsilon_2) x^2 = w}$ . If the signs are different there are no solutions, since ${w}$ is nonzero. Otherwise the equation is ${2 \epsilon_1 x^2 = w}$ . Since ${-1}$ is a quadratic nonresidue, one of the choices of sign gives ${0}$ solutions and the other gives ${2}$ solutions. Therefore ${1_A * 1_A(g) = 2}$ .