Nonexistence of a distance-regular graph with intersection array $\{135, 128, 16; 1, 16, 120\}$¶

We will show that a distance-regular graph with intersection array $\{135, 128, 16; 1, 16, 120\}$ does not exist.

In [1]:

import drg

Such a graph would have $1360$ vertices.

In [2]:

p = drg.DRGParameters([135, 128, 16], [1, 16, 120])
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. The graph would not be $Q$-polynomial, but we still have $q^3_{33} = 0$.

In [4]:

p.kreinParameters()

Out[4]:

0: [  1   0   0   0]
   [  0 306   0   0]
   [  0   0 900   0]
   [  0   0   0 153]

1: [     0      1      0      0]
   [     1     68    220     17]
   [     0    220 1700/3  340/3]
   [     0     17  340/3   68/3]

2: [     0      0      1      0]
   [     0  374/5  578/3 578/15]
   [     1  578/3    610  289/3]
   [     0 578/15  289/3 272/15]

3: [     0      0      0      1]
   [     0     34  680/3  136/3]
   [     0  680/3 1700/3  320/3]
   [     1  136/3  320/3      0]

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 mutually adjacent vertices $u, v, w$. Note that we have $a_1 = 6$, so such triples must exist. The parameter $a$ will denote the number of vertices adjacent to all of $u, v, w$.

In [6]:

S111 = p.tripleEquations(1, 1, 1, params = {"a": (1, 1, 1)})
S111

Out[6]:

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

1: [      0       1       0       0]
   [      1       a  -a + 5       0]
   [      0  -a + 5 a + 123       0]
   [      0       0       0       0]

2: [              0               0               0               0]
   [              0          -a + 5         a + 123               0]
   [              0         a + 123 19/8*a + 4641/8 -27/8*a + 967/8]
   [              0               0 -27/8*a + 967/8   27/8*a + 57/8]

3: [              0               0               0               0]
   [              0               0               0               0]
   [              0               0 -27/8*a + 967/8   27/8*a + 57/8]
   [              0               0   27/8*a + 57/8  -27/8*a + 71/8]

The number of vertices at distance $3$ from all of $u, v, w$ should be a nonnegative integer. Nonnegativity is only achieved when $a = 0, 1, 2$, however integrality is not achieved in any of these cases.

In [7]:

a = S111[1, 1, 1]
[S111[3, 3, 3].subs(a == x) for x in [0, 1, 2, 3]]

Out[7]:

[71/8, 11/2, 17/8, -5/4]

We thus conclude that a graph with intersection array $\{135, 128, 16; 1, 16, 120\}$ does not exist.