#
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 \begin{equation}n-1-rc_2 = a_1-c_2.\label{eq-n1rc2}\tag{4.4.1}\end{equation} 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

\begin{equation}2\le r\le n-1.\label{eq-rbnd}\tag{4.4.2}\end{equation} 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 \begin{equation}1\le c_2 \le \left\lfloor\frac{n-1}{r-1}\right\rfloor\label{eq-c2bnd}\tag{4.4.3}\end{equation}
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 \begin{equation}m_\th = \frac{(r-1)n(-\tau)}{\th -\tau}.\label{eq-mult}\tag{4.4.4}\end{equation}
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 \begin{equation}(\th-\tau)^2 = \de^2+4(n-1) = (a_1-c_2)^2+4(n-1)\label{eq-discr}\tag{4.4.5}\end{equation} 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.