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 local eigenvalues nonexistence check, as it turns out that their multiplicity cannot be integral. Instead, we will use triple intersection numbers to prove nonexistence.

In [5]:

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

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.