Loading [MathJax]/extensions/TeX/newcommand.js
\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.