Notebook

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

%display latex
import drg

Such a graph would have $1360$ vertices.

In [2]:

p = drg.DRGParameters([135, 128, 16], [1, 16, 120])
p.order()

Out[2]:

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

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

$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{aligned}0: &\ \left(\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 0 & 306 & 0 & 0 \\ 0 & 0 & 900 & 0 \\ 0 & 0 & 0 & 153 \end{array}\right) \\ 1: &\ \left(\begin{array}{rrrr} 0 & 1 & 0 & 0 \\ 1 & 68 & 220 & 17 \\ 0 & 220 & \frac{1700}{3} & \frac{340}{3} \\ 0 & 17 & \frac{340}{3} & \frac{68}{3} \end{array}\right) \\ 2: &\ \left(\begin{array}{rrrr} 0 & 0 & 1 & 0 \\ 0 & \frac{374}{5} & \frac{578}{3} & \frac{578}{15} \\ 1 & \frac{578}{3} & 610 & \frac{289}{3} \\ 0 & \frac{578}{15} & \frac{289}{3} & \frac{272}{15} \end{array}\right) \\ 3: &\ \left(\begin{array}{rrrr} 0 & 0 & 0 & 1 \\ 0 & 34 & \frac{680}{3} & \frac{136}{3} \\ 0 & \frac{680}{3} & \frac{1700}{3} & \frac{320}{3} \\ 1 & \frac{136}{3} & \frac{320}{3} & 0 \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 mutually adjacent vertices $u, v, w$. Note that we have $a_1 = 6$, so such triples must exist. The parameter $\alpha$ will denote the number of vertices adjacent to all of $u, v, w$.

In [6]:

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

Out[6]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{aligned}0: &\ \left(\begin{array}{rrrr} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array}\right) \\ 1: &\ \left(\begin{array}{rrrr} 0 & 1 & 0 & 0 \\ 1 & \alpha & -\alpha + 5 & 0 \\ 0 & -\alpha + 5 & \alpha + 123 & 0 \\ 0 & 0 & 0 & 0 \end{array}\right) \\ 2: &\ \left(\begin{array}{rrrr} 0 & 0 & 0 & 0 \\ 0 & -\alpha + 5 & \alpha + 123 & 0 \\ 0 & \alpha + 123 & \frac{19}{8} \, \alpha + \frac{4641}{8} & -\frac{27}{8} \, \alpha + \frac{967}{8} \\ 0 & 0 & -\frac{27}{8} \, \alpha + \frac{967}{8} & \frac{27}{8} \, \alpha + \frac{57}{8} \end{array}\right) \\ 3: &\ \left(\begin{array}{rrrr} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & -\frac{27}{8} \, \alpha + \frac{967}{8} & \frac{27}{8} \, \alpha + \frac{57}{8} \\ 0 & 0 & \frac{27}{8} \, \alpha + \frac{57}{8} & -\frac{27}{8} \, \alpha + \frac{71}{8} \end{array}\right) \\\end{aligned}$

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

In [7]:

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

Out[7]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\frac{71}{8}, \frac{11}{2}, \frac{17}{8}, -\frac{5}{4}\right]$

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