Notebook

Nonexistence of a distance-regular graph with intersection array $\{55, 54, 50, 35, 10; 1, 5, 20, 45, 55\}$¶

We will show that a distance-regular graph with intersection array $\{55, 54, 50, 35, 10; 1, 5, 20, 45, 55\}$ does not exist. The existence of such a graph would give a counterexample to a conjecture by MacLean and Terwilliger, see Bipartite distance-regular graphs: The $Q$-polynomial property and pseudo primitive idempotents by M. Lang.

In [1]:

%display latex
import drg

Such a graph would be bipartite with $3500$ vertices.

In [2]:

p = drg.DRGParameters([55, 54, 50, 35, 10], [1, 5, 20, 45, 55])
show(p.is_bipartite())
show(p.order())

$\newcommand{\Bold}[1]{\mathbf{#1}}\mathrm{True}$

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

We see that all intersection numbers are nonnegative integers.

In [3]:

p.show_distancePartitions(vertex_size=650)

The Krein parameters are also nonnegative. Many Krein parameters are zero - in particular, the graph would be $Q$-polynomial for the natural ordering of the eigenvalues.

In [4]:

p.kreinParameters()

Out[4]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{aligned}0: &\ \left(\begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 132 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1617 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1617 & 0 & 0 \\ 0 & 0 & 0 & 0 & 132 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right) \\ 1: &\ \left(\begin{array}{rrrrrr} 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & \frac{50}{3} & \frac{343}{3} & 0 & 0 & 0 \\ 0 & \frac{343}{3} & \frac{2450}{3} & 686 & 0 & 0 \\ 0 & 0 & 686 & \frac{2450}{3} & \frac{343}{3} & 0 \\ 0 & 0 & 0 & \frac{343}{3} & \frac{50}{3} & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right) \\ 2: &\ \left(\begin{array}{rrrrrr} 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & \frac{28}{3} & \frac{200}{3} & 56 & 0 & 0 \\ 1 & \frac{200}{3} & \frac{2380}{3} & 700 & 56 & 0 \\ 0 & 56 & 700 & \frac{2380}{3} & \frac{200}{3} & 1 \\ 0 & 0 & 56 & \frac{200}{3} & \frac{28}{3} & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \end{array}\right) \\ 3: &\ \left(\begin{array}{rrrrrr} 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 56 & \frac{200}{3} & \frac{28}{3} & 0 \\ 0 & 56 & 700 & \frac{2380}{3} & \frac{200}{3} & 1 \\ 1 & \frac{200}{3} & \frac{2380}{3} & 700 & 56 & 0 \\ 0 & \frac{28}{3} & \frac{200}{3} & 56 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{array}\right) \\ 4: &\ \left(\begin{array}{rrrrrr} 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & \frac{343}{3} & \frac{50}{3} & 1 \\ 0 & 0 & 686 & \frac{2450}{3} & \frac{343}{3} & 0 \\ 0 & \frac{343}{3} & \frac{2450}{3} & 686 & 0 & 0 \\ 1 & \frac{50}{3} & \frac{343}{3} & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \end{array}\right) \\ 5: &\ \left(\begin{array}{rrrrrr} 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 132 & 0 \\ 0 & 0 & 0 & 1617 & 0 & 0 \\ 0 & 0 & 1617 & 0 & 0 & 0 \\ 0 & 132 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 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 vertices $u, v, w$ at mutual distances $2$. Note that we have $p^2_{22} = 243$, so such triples must exist. The parameter $\alpha$ will denote the number of vertices adjacent to all of $u, v, w$.

In [6]:

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

Out[6]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{aligned}0: &\ \left(\begin{array}{rrrrrr} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right) \\ 1: &\ \left(\begin{array}{rrrrrr} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & \alpha & 0 & -\alpha + 5 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & -\alpha + 5 & 0 & \alpha + 45 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right) \\ 2: &\ \left(\begin{array}{rrrrrr} 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 20 \, \alpha + 92 & 0 & -20 \, \alpha + 150 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & -20 \, \alpha + 150 & 0 & 20 \, \alpha + 200 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right) \\ 3: &\ \left(\begin{array}{rrrrrr} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & -\alpha + 5 & 0 & \alpha + 45 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & \alpha + 45 & 0 & 11 \, \alpha + 1055 & 0 & -12 \, \alpha + 160 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & -12 \, \alpha + 160 & 0 & 12 \, \alpha + 15 \end{array}\right) \\ 4: &\ \left(\begin{array}{rrrrrr} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & -20 \, \alpha + 150 & 0 & 20 \, \alpha + 200 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 20 \, \alpha + 200 & 0 & -20 \, \alpha + 605 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right) \\ 5: &\ \left(\begin{array}{rrrrrr} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & -12 \, \alpha + 160 & 0 & 12 \, \alpha + 15 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 12 \, \alpha + 15 & 0 & -12 \, \alpha + 20 \end{array}\right) \\\end{aligned}$

The number of vertices at distance $5$ from all of $u, v, w$ is a nonnegative integer, implying that the parameter $\alpha$ is either $0$ or $1$.

In [7]:

show(S222[1, 1, 1])
show(S222[5, 5, 5])

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

$\newcommand{\Bold}[1]{\mathbf{#1}}-12 \, \alpha + 20$

Let us now consider the set $A$ of common neighbours of $u$ and $v$, and the set $B$ of vertices at distance $2$ from both $u$ and $v$. Their sizes are given by the intersection numbers $p^2_{11}$ and $p^2_{22}$.

In [8]:

show(p.p[2, 1, 1])
show(p.p[2, 2, 2])

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

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

By the above, each vertex in $B$ has at most one neighbour in $A$, so there are at most $243$ edges between $A$ and $B$. However, each vertex in $A$ is adjacent to both $u$ and $v$, and the other $k - 2 = 53$ neighbours are in $B$, amounting to a total of $5 \cdot 53 = 265$ edges. We have arrived to a contradiction, and we must conclude that a graph with intersection array $\{55, 54, 50, 35, 10; 1, 5, 20, 45, 55\}$ does not exist.