Notebook

Nonexistence of a distance-regular graph with intersection array $\{104, 70, 25; 1, 7, 80\}$¶

We will show that a distance-regular graph with intersection array $\{104, 70, 25; 1, 7, 80\}$ does not exist.

In [1]:

%display latex
import drg

Such a graph would have $1470$ vertices.

In [2]:

p = drg.DRGParameters([104, 70, 25], [1, 7, 80])
p.order()

Out[2]:

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

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 be formally self-dual for the natural ordering of eigenspaces and thus also $Q$-polynomial, so we have $q^3_{11} = q^1_{13} = q^1_{31} = 0$.

In [4]:

p.kreinParameters()

Out[4]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{aligned}0: &\ \left(\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 0 & 104 & 0 & 0 \\ 0 & 0 & 1040 & 0 \\ 0 & 0 & 0 & 325 \end{array}\right) \\ 1: &\ \left(\begin{array}{rrrr} 0 & 1 & 0 & 0 \\ 1 & 33 & 70 & 0 \\ 0 & 70 & 720 & 250 \\ 0 & 0 & 250 & 75 \end{array}\right) \\ 2: &\ \left(\begin{array}{rrrr} 0 & 0 & 1 & 0 \\ 0 & 7 & 72 & 25 \\ 1 & 72 & 742 & 225 \\ 0 & 25 & 225 & 75 \end{array}\right) \\ 3: &\ \left(\begin{array}{rrrr} 0 & 0 & 0 & 1 \\ 0 & 0 & 80 & 24 \\ 0 & 80 & 720 & 240 \\ 1 & 24 & 240 & 60 \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"])

Let $w, x, y, z$ be vertices such that $x$ is adjacent to $y$ and $z$, $y$ is at distance $2$ from $w$ and $z$, and $w$ is at distance $3$ from $x$. Note that we have $p^1_{12} = 70$ and $p^1_{32} = 250$, so such vertices must exist. We first compute the triple intersection numbers with respect to $x, y, z$. The parameter $\alpha$ will denote the number of vertices adjacent to $x, y, z$.

In [6]:

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

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 & 0 & 1 & 0 \\ 0 & \alpha & -\alpha + 33 & 0 \\ 1 & -\alpha + 33 & \alpha + 36 & 0 \\ 0 & 0 & 0 & 0 \end{array}\right) \\ 2: &\ \left(\begin{array}{rrrr} 0 & 0 & 0 & 0 \\ 0 & -\alpha + 6 & \alpha + 39 & 25 \\ 0 & \alpha + 39 & 24 \, \alpha + 306 & -25 \, \alpha + 375 \\ 0 & 25 & -25 \, \alpha + 375 & 25 \, \alpha - 150 \end{array}\right) \\ 3: &\ \left(\begin{array}{rrrr} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & -25 \, \alpha + 400 & 25 \, \alpha - 150 \\ 0 & 0 & 25 \, \alpha - 150 & -25 \, \alpha + 225 \end{array}\right) \\\end{aligned}$

From $[2\ 1\ 1] \ge 0$ and $[3\ 2\ 3] \ge 0$, it follows that there is a single solution with $\alpha = 6$ and therefore $[3\ 2\ 3] = 0$, implying that $w$ cannot be at distance $3$ from $z$ for any choice of $w, x, y, z$ as above.

We now compute the triple intersection numbers with respect to $w, x, y$. The parameter $\beta$ will denote the number of vertices at distances $(3, 1, 2)$ from $w, x, y$.

In [7]:

p.tripleEquations(3, 2, 1, params={"beta": (3, 1, 2)})

Out[7]:

$\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 & 1 & 0 \end{array}\right) \\ 1: &\ \left(\begin{array}{rrrr} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 7 & 5 \, \beta - 27 & -5 \, \beta + 100 \\ 0 & 0 & -5 \, \beta + 99 & 5 \, \beta - 75 \end{array}\right) \\ 2: &\ \left(\begin{array}{rrrr} 0 & 0 & 0 & 0 \\ 1 & \beta + 9 & -\beta + 70 & 0 \\ 0 & -\beta + 63 & -24 \, \beta + 882 & 25 \, \beta - 225 \\ 0 & 0 & 25 \, \beta - 210 & -25 \, \beta + 450 \end{array}\right) \\ 3: &\ \left(\begin{array}{rrrr} 0 & 1 & 0 & 0 \\ 0 & -\beta + 24 & \beta & 0 \\ 0 & \beta & 19 \, \beta - 135 & -20 \, \beta + 375 \\ 0 & 0 & -20 \, \beta + 360 & 20 \, \beta - 300 \end{array}\right) \\\end{aligned}$

From $[3\ 3\ 2] \ge 0$ and $[1\ 3\ 3] \ge 0$, it follows that $15 \le \beta \le 18$. This would imply the existence of a vertex $z$ as above that is at distance $3$ from $w$ - a contradiction! We thus conclude that a distance-regular graph with intersection array $\{104, 70, 25; 1, 7, 80\}$ does not exist.