\( \newcommand\al{\alpha} \newcommand\be{\beta} \newcommand\de{\delta} \newcommand\De{\Delta} \newcommand\eps{\epsilon} \newcommand\ga{\gamma} \newcommand\Ga{\Gamma} \newcommand\ka{\kappa} \newcommand\la{\lambda} \newcommand\La{\Lambda} \newcommand\om{\omega} \newcommand\Om{\Omega} \newcommand\sg{\sigma} \newcommand\Sg{\Sigma} \renewcommand\th{\theta} %--- Latex uses \th for a Norse character \newcommand\Th{\Theta} \newcommand\vphi{\varphi} % % some calligraphy % \newcommand\cA{{\mathcal A}} \newcommand\cB{{\mathcal B}} \newcommand\cC{{\mathcal C}} \newcommand\cD{{\mathcal D}} \newcommand\cE{{\mathcal E}} \newcommand\cF{{\mathcal F}} \newcommand\cG{{\mathcal G}} \newcommand\cH{{\mathcal H}} \newcommand\cI{{\mathcal I}} \newcommand\cJ{{\mathcal J}} \newcommand\cK{{\mathcal K}} \newcommand\cL{{\mathcal L}} \newcommand\cM{{\mathcal M}} \newcommand\cN{{\mathcal N}} \newcommand\cO{{\mathcal O}} \newcommand\cP{{\mathcal P}} \newcommand\cQ{{\mathcal Q}} \newcommand\cR{{\mathcal R}} \newcommand\cS{{\mathcal S}} \newcommand\cT{{\mathcal T}} \newcommand\cU{{\mathcal U}} \newcommand\cV{{\mathcal V}} % % fields and rings (and a semigroup) % \newcommand\cx{{\mathbb C}}% complexes \newcommand\fld{{\mathbb F}} \newcommand\flde{{\mathbb E}} \newcommand\ints{{\mathbb Z}} \newcommand\nn{{\mathbb N}}%non-negative integers \newcommand\re{{\mathbb R}}%reals \newcommand\rats{{\mathbb Q}} % % the really useful stuff % \newcommand\comp[1]{{\mkern2mu\overline{\mkern-2mu#1}}} \newcommand\diff{\mathbin{\mkern-1.5mu\setminus\mkern-1.5mu}}% for \setminus \newcommand\res{\mathbin{\mkern-2.0mu\restriction\mkern-2.0mu}} \newcommand\sbs{\subseteq} \newcommand\sps{\supseteq} \newcommand\seq[3]{#1_{#2},\ldots,#1_{#3}} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\row}{row} \newcommand\pmat[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand\cprod{\mathbin{\square}} \newcommand\gbin[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} % % matrix theory % \newcommand\ip[2]{\langle#1,#2\rangle} \newcommand\one{{\bf1}} \DeclareMathOperator{\rk}{rk} \DeclareMathOperator{\tr}{tr} \DeclareMathOperator{\col}{col} \newcommand\mat[3]{\mathrm{Mat}_{#1\times #2}(#3)} \newcommand\sm[3]{\sum_{#1=#2}^{#3}} % % some group theory % \newcommand\aut[1]{{\rm Aut}(#1)} \newcommand\fx[1]{{\rm fix}(#1)}% ch2 \newcommand\grp[1]{\langle #1\rangle} \newcommand\nrml{\vartriangleleft} \newcommand\nrmleq{\trianglelefteq} \DeclareMathOperator{\Sym}{Sym} \newcommand\sym[1]{\Sym(#1)} \DeclareMathOperator{\Alt}{Alt} \newcommand\alt[1]{\Alt(#1)} \)

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.