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]:

import drg

Such a graph would have $1600$ vertices.

In [2]:

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

Out[2]:

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]:

0: [   1    0    0    0]
   [   0   78    0    0]
   [   0    0  234    0]
   [   0    0    0 1287]

1: [   0    1    0    0]
   [   1    8   36   33]
   [   0   36    0  198]
   [   0   33  198 1056]

2: [   0    0    1    0]
   [   0   12    0   66]
   [   1    0   68  165]
   [   0   66  165 1056]

3: [   0    0    0    1]
   [   0    2   12   64]
   [   0   12   30  192]
   [   1   64  192 1030]

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 $a$ will denote the number of vertices at distance $3$ from all of $u, v, w$.

In [6]:

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

Out[6]:

0: [0 0 0 0]
   [0 0 0 0]
   [0 0 0 0]
   [0 0 0 1]

1: [        0         0         0         0]
   [        0         0         0         0]
   [        0         0 3*a + 186 -3*a + 12]
   [        0         0 -3*a + 12  3*a + 24]

2: [          0           0           0           0]
   [          0           0   3*a + 186   -3*a + 12]
   [          0   3*a + 186 -10*a + 832    7*a + 38]
   [          0   -3*a + 12    7*a + 38   -4*a - 17]

3: [        0         0         0         1]
   [        0         0 -3*a + 12  3*a + 24]
   [        0 -3*a + 12  7*a + 38 -4*a - 17]
   [        1  3*a + 24 -4*a - 17         a]

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

In [7]:

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

-4*a - 17
a

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