Notebook

Nonexistence of a distance-regular graph with intersection array $\{234, 165, 12; 1, 30, 198\}$¶

We will show that a distance-regular graph with intersection array $\{234, 165, 12; 1, 30, 198\}$ does not exist.

In [1]:

%display latex
import drg

Such a graph would have $1600$ vertices.

In [2]:

p = drg.DRGParameters([234, 165, 12], [1, 30, 198])
p.order()

Out[2]:

$\newcommand{\Bold}[1]{\mathbf{#1}}1600$

We see that all intersection numbers are nonnegative integers.

In [3]:

p.show_distancePartitions(vertex_size=650)

The Krein parameters are also nonnegative. We have $q^1_{22} = q^2_{12} = q^2_{21} = 0$, so the graph would be $Q$-polynomial with respect to the ordering of the eigenvalues $0, 2, 3, 1$.

In [4]:

p.kreinParameters()

Out[4]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{aligned}0: &\ \left(\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 0 & 78 & 0 & 0 \\ 0 & 0 & 234 & 0 \\ 0 & 0 & 0 & 1287 \end{array}\right) \\ 1: &\ \left(\begin{array}{rrrr} 0 & 1 & 0 & 0 \\ 1 & 8 & 36 & 33 \\ 0 & 36 & 0 & 198 \\ 0 & 33 & 198 & 1056 \end{array}\right) \\ 2: &\ \left(\begin{array}{rrrr} 0 & 0 & 1 & 0 \\ 0 & 12 & 0 & 66 \\ 1 & 0 & 68 & 165 \\ 0 & 66 & 165 & 1056 \end{array}\right) \\ 3: &\ \left(\begin{array}{rrrr} 0 & 0 & 0 & 1 \\ 0 & 2 & 12 & 64 \\ 0 & 12 & 30 & 192 \\ 1 & 64 & 192 & 1030 \end{array}\right) \\\end{aligned}$

We check the remaining known feasibility conditions. We skip the sporadic nonexistence check since the intersection array is already included.

In [5]:

p.check_feasible(skip=["sporadic"])

We now compute the triple intersection numbers with respect to three vertices $u, v, w$ at mutual distances $3$. Note that we have $p^3_{33} = 8$, so such triples must exist. The parameter $\alpha$ will denote the number of vertices at distance $3$ from all of $u, v, w$.

In [6]:

S333 = p.tripleEquations(3, 3, 3, params={"alpha": (3, 3, 3)})
S333

Out[6]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{aligned}0: &\ \left(\begin{array}{rrrr} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right) \\ 1: &\ \left(\begin{array}{rrrr} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 3 \, \alpha + 186 & -3 \, \alpha + 12 \\ 0 & 0 & -3 \, \alpha + 12 & 3 \, \alpha + 24 \end{array}\right) \\ 2: &\ \left(\begin{array}{rrrr} 0 & 0 & 0 & 0 \\ 0 & 0 & 3 \, \alpha + 186 & -3 \, \alpha + 12 \\ 0 & 3 \, \alpha + 186 & -10 \, \alpha + 832 & 7 \, \alpha + 38 \\ 0 & -3 \, \alpha + 12 & 7 \, \alpha + 38 & -4 \, \alpha - 17 \end{array}\right) \\ 3: &\ \left(\begin{array}{rrrr} 0 & 0 & 0 & 1 \\ 0 & 0 & -3 \, \alpha + 12 & 3 \, \alpha + 24 \\ 0 & -3 \, \alpha + 12 & 7 \, \alpha + 38 & -4 \, \alpha - 17 \\ 1 & 3 \, \alpha + 24 & -4 \, \alpha - 17 & \alpha \end{array}\right) \\\end{aligned}$

We now note that since $\alpha$ must be nonnegative, the number of vertices at distances $2, 3, 3$ from $u, v, w$ must be negative - contradiction

In [7]:

show(S333[2, 3, 3])
show(S333[3, 3, 3])

$\newcommand{\Bold}[1]{\mathbf{#1}}-4 \, \alpha - 17$

$\newcommand{\Bold}[1]{\mathbf{#1}}\alpha$

We thus conclude that a graph with intersection array $\{234, 165, 12; 1, 30, 198\}$ does not exist.