# Section4.4Drackns: Generating Parameter Sets

We are interested in distance-regular antipodal covers of $K_n$. We construct a cover of index $r$ of a graph $X$ (or an $r$-fold cover) as follows. Choose a function $f$ from the arcs (ordered pairs of adjacent vertices of $X$) to the symmetric group $\sym r$, such that

$F((v,u)) =f((u,v))^{-1}$
The vertex set of the cover $X^f$ is
$V(X)\times \{1,\ldots,r\}$
and $(u,i)\sim (v,j)$ if $j = i^{f(u,v)}$. Less formally, we replace each vertex of $V(X)$ by a coclique of size $r$, and cocliques corresponding to adjacent vertices are joined by a matching of size $r$. The $r$-cocliques are called the fibers of the cover.

A cover $X^f$ is antipodal if its diameter is $d$ and two vertices are in the same fiber if and only they are at distance $d$. The 3-cube is an antipodal cover of $K_4$ with index two and diameter three. The line graph of the Petersen graph is an antipodal cover of $K_5$ with index and diameter three.

Here we are concerned with distance-regular antipodal covers of complete graphs $K_n$. Such covers must have diameter three. There are four obvious parameters $(n,r,a_1,c_2)$, although they are not independent. Counting edges joining neighbors of $u$ to vertices at distance two from $u$, we get

$n(n-2-a_2) = n(r-1)c_2$
whence
$$n-1-rc_2 = a_1-c_2.\label{eq-n1rc2}\tag{4.4.1}$$
The difference $a_1-c_2$ occurs frequently, and we denote it by $\de$. It is not too hard to show that an antipodal cover of $K_n$ is distance regular if its diameter is three and any two distinct non-adjacent vertices have $c_2$ common neighbors.

Our basic problem is to determine the parameter triples $(n,r,c_2)$ for which a cover exists. This is an impossible problem, so we settle for generating parameter sets for which there is a good chance that a cover exists. Here our first design question surfaces: do we want to order our parameters by $n$ and then $r$ (lexicographically), or by $nr$ then $r$ (for example). We arbitrarily select the first approach.

As a first step we aim to generate a list of quadruples $(n,r,a_1,c_2)$. Now we know that

$$2\le r\le n-1.\label{eq-rbnd}\tag{4.4.2}$$
What about $c_2$? The neighborhood of a vertex induces a regular graph on $n-1$ vertices with valency $a_1$, whence $na_1$ must be even. From ((4.4.1)) we have
$n-1-a_1 = (r-1)c_2,$
from which we infer that if $n$ is odd and $r$ is even, then $c_2$ must be even. We also have
$$1\le c_2 \le \left\lfloor\frac{n-1}{r-1}\right\rfloor\label{eq-c2bnd}\tag{4.4.3}$$

So we will generate a sequence of 4-tuples, and filter out the ones that obviously do not work. The most useful condition rests on the formulas for the multiplicities of the eigenvalues. As a distance-regular graph with diameter three, a drackn has exactly four distinct eigenvalues

$n > \th > -1 > \tau$
where $n$ is simple, $-1$ has multiplicity $n-1$ and $-\th\tau=n-1$. The eigenvalues $\th$ and $\tau$ are the zeros of
$t^2 -\de t - (n-1).$
It is their multiplicities that interest us. With an obvious notation we have
\begin{align*} rn &= 1 + (n-1) +m_\th+m_\tau\\ 0 &= (n-1) +(n-1)(-1) +m_\th\th+m_\tau\tau \end{align*}
and therefore
$$m_\th = \frac{(r-1)n(-\tau)}{\th -\tau}.\label{eq-mult}\tag{4.4.4}$$

Two cases arise. First, if $\th$ and $\tau$ are not integers, then

$\th=\sqrt{n-1},\quad \tau=-\sqrt{n-1}$
and their multiplicities are equal to $n(r-1)/2$. Otherwise they are integers and consequently the discriminant
$$(\th-\tau)^2 = \de^2+4(n-1) = (a_1-c_2)^2+4(n-1)\label{eq-discr}\tag{4.4.5}$$
must be a perfect square. (Note that $\de=n-1-rc_2$.) If this is a perfect square we can determine $\th$ and $\tau$, and then check that our formula for $m_th$ is an integer.

How do we generate 4-tuples? The simplest approach is to use CartesianProduct, but a more efficient strategy is to use generators.

Now we can generate a selected family of 4-tuples. There are other conditions that must hold, we write a predicate for each of these and then write a function that takes a 4-tuple and applies each term in a list of predicates. Note that, when a parameter set is eliminated we need to know at least one of the predicates that it fails.

There is a very strong case to be made that a better parameterization is available. The idea is to search on triples

$(-\tau,\theta, r)$
Our approach above throws out most triples because $(a_1-c_2)^2+4(n-1)$ is not a perfect square. Our alternative approach only produces triples where this condition is satisfied. We need to treat separately the case where $m_\th=m_\tau$, (equivalently $\de=0$) but this makes sense combinatorially. If we want the parameters for covers of $K_n$ with index $r$, then we filter through the pairs $(-\tau, \theta)$ where $\theta$ runs over the elements of divisors(n-1) such that the Krein bound holds.