In the following few pages we give the current version of Section
3.14 and the first part of 3.15 (pp. 113-120).
For the position of distance-regular graphs in the metric
hierarchy, see
.SC Koolen
.[[
Koolen Master's thesis metric properties 1990
.]],
.SC Koolen & Shpectorov
.[[
Koolen Shpectorov 1994 positive eigenvalue
.]],
.SC Shpectorov
.[[
Shpectorov isometric halved cube
.]].
.bp
.nr H1 3
.nr H2 13
.Nh "Root graphs"
A
.I
root representation
.R
.Xx "root representation"
of a graph is an integral affine (2,4)-representation,
i.e., a representation such that the
squared distances
$[ gam , del ] = ( gam bar - del bar , gam bar - del bar )$
of the images of all
$gam , del mo GAM$ are even integers and satisfy
.EQ C
[ gam , del ] = 2i ~ if ~ d ( gam , del ) = i <= 2.
.EN
A connected graph having a root representation is called a
.I
root graph,
.R
.Xx "root graph"
and a
.I
strict root graph
.R
.Xx "strict root graph"
if the representation is strict, i.e.,
.EQ C
[ gam , del ] = 2i <= 4 iff d ( gam , del ) = i <= 2.
.EN
The name reflects the fact that the lattice $Ll ( GAM )$
of a root representation of $GAM$, defined in
Section 3.9, is a root lattice:
.NH 3
.R
$Pr$.
.I
Let $GAM$ be a root graph. Then
$Ll ( GAM )$ is a root lattice. Moreover,
if $GAM$ is locally connected, then
$Ll ( GAM )$ is irreducible.
.Bop
Since $GAM$ is connected,
$Ll ( GAM )$
is generated by the norm 2 vectors
$gam bar - del bar$ ($gam , del mo GAM$, $gam adj del$),
and is therefore a root lattice. Now suppose that
$Ll ( GAM )$ is the direct sum of two lattices
$Ll sub 1$ and $Ll sub 2$.
If we call an edge $gam del$ of \fItype\fP $i$
if the norm 2 vector $gam bar - del bar$ is in
$Ll sub i$ then each edge is either of type 1
or of type 2. If
$alpha beta gam$ is a triangle, then
$( alpha bar - beta bar , alpha bar - gam bar ) = 1$
so that edges in the same triangle have the same type.
If $GAM$ is locally connected, then this implies
that all edges have the same type, whence
$Ll ( GAM ) = Ll sub 1$ or
$Ll ( GAM ) = Ll sub 2$, showing that
$Ll ( GAM )$ is irreducible.
.Eop
.LP
Using the classification of root lattices we shall give
a complete characterization of amply regular root graphs
with $mu > 1$ in the next section. This leads in the next
chapter to an important
classification theorem for distance-regular graphs (Theorem $DrgRep$.11).
$Re$. Related questions are considered by
.SC Terwilliger
.[[
Terwilliger root system graphs rsg
.]],
who considers structure theorems for (not necessarily regular)
graphs having a spherical representation such that $[ gam , del ]$
is an even integer for all $gam , del mo GAM$ and $[ gam , del ] = 2$
if and only if $d ( gam , del ) = 1$.
Root graphs generalize graphs with smallest eigenvalue $X>= -2$:
.NH 3
.R
$Th$.
.IP (i)
.I
Every graph with smallest eigenvalue $X>= -2$ is a root graph.
.IP (ii)
.I
A regular root graph of diameter $X<= 2$ has smallest eigenvalue $X>= -2$.
.Bop
(i) A graph with smallest eigenvalue $X>= -2$ has a spherical
$(2,1,0)$-representation which is a root representation.
.br
(ii) By Proposition 3.5.6\|(ii), a regular root graph $GAM$
of diameter $X<= 2$ has a spherical $(p,p-1,p-2)$-representation
for some $p > 0$; thus by Proposition 3.5.3\|(iii),
$GAM$ has smallest eigenvalue $X>= -2$.
.Eop
The graphs $K sub 1,n$ are root graphs of diameter 2 with smallest
eigenvalue $- sqrt n$, so regularity is required in part (ii) above.
.Nb "Examples"
The representation of $E sub 7 ( 1 )$
defined in \(sc3.11 is a root representation,
so that any induced subgraph of $E sub 7 ( 1 )$
is a root graph. (However, $E sub 8 ( 1 )$, as
given in \(sc3.11, contains vertices with squared distance
6 having a common neighbour, and hence defines no
root representation). Further examples of root graphs
are the \fIcode graphs\fP $GAM ( C )$,
.Xx "code graph"
defined by the words
of a binary code $C$ of length $n$, words being
adjacent if they differ in two entries
(i.e., if their Hamming distance is 2); they
have a natural representation by (0,1)-vectors in
$Rr sup n$. We mention in particular
the following amply regular code graphs.
.LP
.IP (i)
The
.I
half-cube
.R
.Xx "half-cube"
$D sub n,n (1)$ is the code graph of the
binary code consisting of all even weight
words of length $n$.
$D sub n,n (1)$ has
$2 sup {n-1}$ vertices, valency
$Binom(n,2)$ and $mu = 6$. The graph
$D sub 5,5 (1)$ is isomorphic to the
Clebsch graph described in Section 3.11.
.Xx "Clebsch graph"
.IP (ii)
The
.I
Johnson graph
.R
.Xx "Johnson graph"
$J ( n , d )$ is the code graph of the
binary code consisting of all words of
length $n$ and weight $d$.
$J (n,d)$ has $Binom(n,d)$ vertices, valency $d ( n - d )$ and
$mu = 4$. In particular $(d = 1)$, $n$-cliques are code graphs.
.IP (iii)
The
.I
icosahedron
.R
.Xx "icosahedron"
with 12 vertices, valency $5$ and
$mu = 2$ can be viewed as the code
graph of the binary code consisting
of the words 000000, 110000,
001111, 111111, and those obtained by
a cyclic permutation of the first
five entries.
.IP (iv)
The
.I
Shrikhande graph
.R
.Xx "Shrikhande graph"
with 16 vertices, valency 6 and
$mu = 2$ can be viewed as the
code graph of the binary code consisting of the
words 000000, 110000, 010111, 011011 and
those obtained by a cyclic permutation
of the six entries (cf. Example 3.11\|(vi)).
.IP (v)
The
.I
Petersen graph
.R
.Xx "Petersen graph"
with 10 vertices, valency 3 and $mu = 1$
can be viewed as the code graph of the binary
code consisting of the words 000000, 100100, 001111
and those obtained by a cyclic permutation
of the six entries (cf. Example 3.11\|(v)).
.IP (vi)
The
.I
dodecahedron
.R
.Xx "dodecahedron"
with 20 vertices, valency 3 and $mu = 1$ can be viewed as the
code graph of the binary code consisting of the words
11000\|00000, 11000\|11000 and their complements and those
obtained by simultaneous cyclic permutation of the first five
and the last five entries.
.IP (vii)
The $g$-\fIgon\fP with $g$ vertices, valency 2 and $mu = 1$
(when $g > 4$) is
the code graph of the binary code consisting of the cyclic
shifts of $1 sup 2 0 sup g-2$.
(An isometric embedding in $D sub g,g (1)$ is given by the cyclic
shifts of $1 sup a 0 sup g-a$ for $a = [g/2]$.)
.IP (viii)
The direct product
$GAM$ of root graphs $GAM sup 1 , ... , GAM sup s$
is a root graph: simply represent $( gam sub 1 , ... , gam sub s )$
by the concatenation of the images of the $gam sub i$.
(Now clearly $Ll ( GAM )$ is the direct sum of
$Ll ( GAM sup 1 ) , ... , Ll ( GAM sup s )$.)
Similarly, the direct product of code graphs is a code graph.
In particular, the
.I
Hamming graphs
.R
.Xx "Hamming graph"
(direct products of cliques) and
.I
Doob graphs
.R
.Xx "Doob graph"
(the direct product of 4-cliques and Shrikhande graphs,
cf. \(sc$ClassGr$.2B) are code graphs.
.IP (ix)
Of course, any induced subgraph of a code graph is again a code graph.
In particular, as subgraphs of $n$-cubes,
the doubled Odd graphs are code graphs.
.LP
We first prove some easy results about the local
structure of root graphs.
.NH 3
.R
$Le$.
.I
Let $GAM$ be a root graph and
$alpha , beta , gam mo GAM$. For the associated
root representation we have
.EQ I \fR(6)\fP 10n
( alpha bar - gam bar , beta bar - gam bar ) = mark
2 - d ( alpha , beta ) >= 0 ~~ if ~ alpha , beta mo GAM ( gam )
.EN
.EQ I \fR(7)\fP
= lineup 3 - d ( alpha , beta ) >= 0 ~~ if ~ alpha mo GAM ( gam ) ,~
beta mo GAM sub 2 ( gam ) ,
.EN
.EQ I \fR(8)\fP
= lineup 4 - d ( alpha , beta ) >= 0 ~~ if ~ alpha , beta mo
GAM sub 2 ( gam ) ,
.EN
provided that $d( alpha , beta ) <= 2$.
In particular, if $gam bar = 0$, then points in
$GAM ( gam )$ are represented by norm $2$ vectors, and points in
$GAM sub 2 ( gam )$ are represented by norm $4$ vectors.
.Bop
By Lemma 3.5.1 we have
.KS
.EQ I "" 10n
( alpha bar - gam bar , beta bar - gam bar ) = mark 1o2 ( [
alpha , gam ] + [ beta , gam ] - [ alpha , beta ] -
[ gam , gam ] )
.EN
.EQ I
= lineup d ( alpha , gam ) + d ( beta , gam ) - d( alpha , beta ) ,
.EN
.KE
which implies (6), (7) and (8). By putting
$alpha = beta$ we obtain the second statement.
.Eop
.NH 3
.R
$Pr$.
.I
Let $GAM$ be a root graph and $gam mo GAM$. Then:
.IP (i)
.I
The local subgraph $GAM ( gam )$ has smallest eigenvalue $X>= -2$.
.IP (ii)
.I
Two nonadjacent points $alpha , beta mo GAM ( gam )$ have at most one
common neighbour in $GAM sub 2 ( gam )$, and such a
neighbour is represented by $alpha bar + beta bar - gam bar$.
.IP (iii)
.I
For $alpha , beta mo GAM$ at distance two, the graph
$GAM ( alpha ) ca GAM ( beta )$ is
complete multipartite with classes of size $1$ or $2$.
.Bop
(i) By Proposition 3.5.6\|(i), $GAM ( gam )$ has
a (2,1,0)-representation. Thus, if $A$ denotes the adjacency
matrix of $GAM ( gam )$, then the Gram matrix
$G = 2I + A$ of the image of $GAM ( gam )$ is
positive semidefinite. This implies (i).
.br
(ii) Now let $alpha , beta mo GAM ( gam )$ be
nonadjacent. If $del mo GAM sub 2 ( gam )$ is a common
neighbour of $alpha$ and $beta$ then Lemma 3.5.1 implies
.EQ C
( del bar - alpha bar , beta bar - gam bar ) = 1o2 ([ del , gam ] +
[ alpha , beta ] - [ del , beta ] - [ alpha , gam ]) =
1o2 (4 + 4 - 2 - 2) = 2.
.EN
Thus the norm of
$( del bar - alpha bar ) - ( beta bar - gam bar )$ is
$[ del , alpha ] - 2( del bar - alpha bar , beta bar - gam bar )
+ [ beta , gam ] = 2 - 4 + 2 = 0$.
Therefore $( del bar - alpha bar ) - ( beta bar - gam bar ) = 0$,
so $del bar = alpha bar + beta bar - gam bar$, and,
by Lemma 3.5.5, $del$ is unique.
This implies (ii).
.br
(iii)
Finally, let $d( alpha , beta ) = 2$. If
$GAM ( alpha ) ca GAM ( beta )$ is not
as claimed in (iii), then it contains three distinct points
$gam , del , del prime$ such that
$del , del prime nm GAM ( gam )$. But this
contradicts part (ii).
.Eop
.NH 3
.R
$Co$.
.I
Let $GAM$ be a root graph, $gam mo GAM$ and $Q$ a quadrangle
in $GAM ( gam )$. Then if $del mo GAM ( gam ) minus Q$ is
adjacent to some but not all vertices of $Q$, the set
$del sup perp ca Q$ is an edge.
.Bop
$Q cu "{" del "}"$ is a connected graph on 5 vertices with
smallest eigenvalue less than $-2$, unless $del sup perp ca Q$
is an edge.
.Eop
.NH 3
.R
$Co$.
.I
Let $GAM$ be a root graph with $mu ( GAM ) = mu$. Then any two
nonadjacent vertices $alpha , beta mo GAM ( gam )$ have either
$mu - 1$ or $mu - 2$ common neighbours in $GAM ( gam )$.
.Bop
Among the $mu$ common neighbours of $alpha$ and $beta$, one is $gam$,
and at most one is in $GAM sub 2 ( gam )$. The remaining
neighbours must be in $GAM ( gam )$.
.Eop
.NH 3
.R
$Le$.
.I
Let $GAM$ be a root graph with $Ll ( GAM ) ib Zz sup n+1$
and $gam$, $del$ vertices at distance two with
$del bar - gam bar = 2e sub 0$, where $e sub 0 = (1,0, ... ,0)$.
Then no vertex of $GAM ( gam ) ca GAM ( del )$ is adjacent to
a vertex of $GAM ( gam ) minus GAM ( del )$.
.Bop
Without loss of generality we may assume that
$gam bar = 0$ and $del bar = 2 e sub 0$.
Lemma 3.14.3 shows that common neighbours of
$gam$ and $del$ are represented by
suitable vectors $e sub 0 +- e sub l$, and,
by permuting the $e sub i$ and changing their
signs if necessary, we may assume that
$M := GAM ( gam ) ca GAM ( del )$ is
represented by the $mu = 2 s + t$
vectors
.EQ C
e sub 0 +- e sub l ~~( l = 1 , ... , s ) ,
~~~ e sub 0 + e sub l ~~( l = s + 1 , ... , s + t ).
.EN
Let $alpha mo M$ so that (for some $i$) $alpha bar = e sub 0 +- e sub i$,
and suppose that $gam$ has a neighbour
$beta nm M$ adjacent with $alpha$.
Then $d ( beta , del ) = 2$; but either
$beta bar = e sub 0 +- e sub j$, $( beta bar , del bar ) = 2$, or
$beta bar = +- e sub i +- e sub j$
$( 0 != j != i != 0 )$, $( beta bar , del bar ) = 0$,
both contradicting Lemma 3.14.3.
Hence no point of $GAM ( gam ) minus GAM ( del )$
is adjacent to a point of $M$.
.Eop
.NH 3
.R
$Pr$.
.I
Let $GAM$ be a root graph with $Ll ( GAM ) ib Zz sup n+1$ for some $n$, and
\fR(*)\fP for no $gam , del mo GAM$ at mutual distance two
do we have $del bar - gam bar = +- 2 e sub i$ for some $i$,
$0 <= i <= n$.
Then $GAM$ has a root representation in $"{"0,1"}" sup n+1$
sending an arbitrary $gam mo GAM$ to $0$.
.Bop
Given a root representation
$rho : gam goesto gam bar = sum gam sub i e sub i$ satisfying (*),
and a vector $u mo Zz sup n+1$, we find new root representations
$rho - u : gam goesto gam bar - u$ and
$vb rho vb : gam goesto sum vb gam sub i vb e sub i$
both satisfying (*). (Indeed, if
$"{" del sub i - gam sub i mo "{" -1,0,1 "}"$ then
$( del sub i - gam sub i ) sup 2 =
( vb del sub i vb - vb gam sub i vb ) sup 2$;
in particular this holds for $d( gam , del ) <= 2$.)
Let $rho$ be a root representation satisfying (*) in
$"{"0,1,...,m"}" sup n+1$, where $m$ is chosen minimal.
Then $m <= 1$, otherwise $vb rho - bold 1 vb$ would be
a representation in $"{"0,1,...,m-1"}"$. Now
$vb rho - rho ( gam ) vb$ is the required representation.
.Eop
.NH 3
.R
$Le$.
.I
Let $GAM$ be a root graph with $Ll ( GAM ) ib Zz sup n+1$
and $mu ( alpha , beta ) >= 2$ for any two vertices $alpha , beta mo GAM$
at distance two. Suppose $d( gam , del ) <= 4$.
\fR(i)\fP If $gam bar = del bar$, then $gam = del$.
\fR(ii)\fP If $[ gam , del ] = 2$ then $gam adj del$.
.Bop
If $d( gam , del ) <= 2$, this is clear.
We first prove part (ii). Assume $[ gam , del ] = 2$.
If $d( gam , del ) = 3$, then choose $eps mo GAM ( gam ) ca GAM sub 2 ( del )$
and shift the representation such that $eps bar = 0$.
We may assume that $gam bar = e sub i + e sub j$ and
$del bar - gam bar = e sub k + e sub l$, with distinct $i,j,k,l$.
The common neighbours of $del$ and $eps$ are represented by certain
$e sub a + e sub b$ with $"{"a,b"}" ib "{"i,j,k,l"}"$,
and since there are at least two of those, it follows that
$gam$ has distance at most one to (at least) one of them, so
that $d( gam , del ) <= 2$, contradiction.
If $d( gam , del ) = 4$, then choose
$eps mo GAM sub 2 ( gam ) ca GAM sub 2 ( del )$
and shift the representation such that $eps bar = 0$.
We may assume that $gam bar = e sub i + e sub j + e sub k + e sub l$
and $del bar = e sub i + e sub j + e sub k + e sub m$.
By the foregoing, no common neighbour of $gam$ and $eps$ is represented
by $e sub a + e sub b$ with $"{"a,b"}" ib "{"i,j,k"}"$,
so the (at least two) vertices in $gam sup perp ca eps sup perp$
are represented by $e sub a + e sub l$ for certain $a mo "{"i,j,k"}"$,
and similarly those in $del sup perp ca eps sup perp$ by
$e sub a + e sub m$ for certain $a mo "{"i,j,k"}"$.
But then some vertex in $gam sup perp ca eps sup perp$
is adjacent to some vertex in $del sup perp ca eps sup perp$,
so that $d( gam , del ) <= 3$, contradiction.
This proves part (ii). But if $gam bar = del bar$,
$gam , del mo GAM sub 2 ( eps )$, then by the above
$gam sup perp ca eps sup perp = del sup perp ca eps sup perp$
and hence $d( gam , del ) <= 2$, contradiction. This proves part (i).
.Eop
.NH 3
.R
$Pr$.
.I
Let $GAM$ be a root graph with $Ll ( GAM ) ib Zz sup n+1$ and
noncomplete $mu$-graphs.
Then for any $gam mo GAM$ the root representation is
uniquely determined by its restriction to $gam sup perp$.
If moreover $mu ( GAM ) = mu$ is constant, then $GAM$ itself is
uniquely determined by the representation of $gam sup perp$.
.Bop
The first claim follows immediately from 3.14.4\|(ii).
If $mu$ is constant, then the representation of $gam sup perp$
determines the structure and representation of $GAM sub 2 ( gam )$:
for any two nonadjacent vertices $alpha , beta mo GAM ( gam )$
that have only $mu - 2$ common neighbours in $GAM ( gam )$, we find
a vertex $del$ represented by $alpha bar + beta bar - gam bar$.
But the restriction of the representation to $GAM sub { X<= 2 } ( gam )$
is injective, and determines the structure of this subgraph,
by Lemma 3.14.9 above. Now vary the vertex $gam$.
.Eop
.Nh "Classification of amply regular root graphs"
Let us first define one more family of graphs, and then show
that all amply regular root graphs with $mu > 1$ are known.
.LP
Let $B(n,s)$ be the subgraph of the halved $(n+2)$-cube
spanned by the $2 Binom(n,s-1) + 2 Binom(n,s)$ vectors of length $n+2$
and either weight $s+2$ starting $11 ...$ or weight $s$ starting
$10 ...$ or $01 ...$ or $00 ...$. Then $B(n,s)$ is a root graph
(indeed, a code graph) with $mu = 4$.
It is regular if and only if $n = 2s-1$, and we put
$B(s) := B(2s-1,s)$. Now $B(s)$ is regular of valency
$s sup 2 + s + 1$, has diameter $s$, and satisfies $c sub i = i sup 2$
($1 <= i <= s$). In particular, $B(1) isom K sub 4$, and
$B(2)$ is one of the subgraphs of the Clebsch graph mentioned in
3.11\|(iii). For $s >= 2$, $Aut B(s)$ is transitive of rank $3s$.
For more details, see
.SC Brouwer & Koolen
.[[
Brouwer Koolen infinite series
.]].
.NH 3
.R
$Th$.
.I
Let $GAM$ be a non-complete regular root graph with
$mu ( GAM ) = mu > 2$.
Then $GAM$ is locally connected and one of the following holds.
.IP (i)
.I
$GAM isom K sub { n times 2 }$, where $mu = 2n - 2 >= 8$.
.IP (ii)
.I
$mu = 6$ and $GAM$ is a half-cube.
.IP (iii)
.I
$mu = 4$ and either $GAM$ is a Johnson graph or $GAM isom B(n)$
for some $n >= 2$.
.IP (iv)
.I
$Ll ( GAM ) isom E sub 6$, $E sub 7$, or $E sub 8$.
.Bop
By Corollary 3.14.6, $GAM$ is locally connected,
and by Proposition 3.14.1,
$Ll ( GAM )$ is irreducible. Now we assume
that we are not in case (iv). Then by Theorem
3.10.4, $Ll ( GAM )$ is isomorphic to
$A sub n$ or $D sub n$; in particular
$Ll ( GAM ) ib Zz sup {n+1} :=
Zz e sub 0 ds Zz e sub 1 ds ... ds Zz e sub n$,
and we may identify vectors in
$Ll ( GAM )$ with $( n + 1 )$-tuples of integers.
.LP
Suppose that $GAM$ contains points $gam , del$ at distance 2
such that the norm 4 vector
$gam bar - del bar$ has the form $+- 2 e sub j$ for some $j$.
Since $GAM$ is locally connected, it follows from
Lemma 3.14.7 that $GAM ( gam ) ca GAM ( del ) = GAM ( gam )$.
Therefore $GAM$ has valency $k = mu$, and $GAM$
is complete multipartite with classes of constant size $s$. But
$GAM ( gam )$ has classes of size 1 or 2 only;
therefore $s <= 2$, and $GAM isom K sub { m times 2 }$ for
some $m >= 3$. If $m > 4$, then (i) holds; if $m = 4$ then
$GAM$ is the halved 4-cube, and if $m = 3$ then $GAM isom J(4,2)$.
[If we do not assume regularity, the conclusion here is that
either $GAM$ is complete multipartite with classes of size 1 or 2, or
$GAM isom K sub 3,1,1,1$.]
.LP
We may now assume that $GAM$ does not contain
points $gam , del$ at distance 2 such that
$gam bar - del bar = +- 2 e sub j$ $( j = 0 , ... , n )$.
Fix $gam mo GAM$. By Proposition 3.14.8 we may assume
that $del bar = sum del sub i e sub i$ with $del sub i mo "{"0,1"}"$
for all $i$ and $del mo GAM$, and that $gam bar = 0$.
.br
Now let $DELTA$ be the graph whose vertices are
the $n + 1$ indices $0,1, ... ,n$,
and whose edges are the pairs $ij$ such that
some point of $GAM ( gam )$ is represented by
$e sub i + e sub j$. Since distinct
points of $GAM ( gam )$ are represented
by distinct vectors (their difference must have
norm 2 or 4) we may identify the point represented
by $e sub i + e sub j$ with the edge $ij$ of $DELTA$.
.br
Let us denote by $S ( del )$ the set
of indices $i$ with $del sub i != 0$.
By Lemma 3.14.3, the points
$del mo GAM sub 2 ( gam )$
are represented by norm 4 vectors
$del bar = del bar - gam bar$, and these must have the form
$e sub i + e sub j + e sub k + e sub l$,
i.e., $S ( del )$ is a 4-set.
The $mu$ common neighbours of $gam$ and
$del$ are certain edges of the subgraph of
$DELTA$ induced on $S ( del )$. By Lemma 3.14.9,
the intersection $GAM ( gam ) ca GAM ( del )$
coincides with the set of edges of
$DELTA$ contained in $S ( del )$, and $del mo GAM sub 2 ( gam )$
is uniquely determined by $S( del )$.
To simplify the notation we shall use the abbreviation
$abcd$ for a 4-set $"{" a , b , c , d "}"$.
.LP
Let us call a set
$S ib "{" 0,1, ... ,n"}"$
.I
special
.R
if there is a point $del mo GAM$ with
.EQ C
S ( del ) = S ,~~ d ( del , gam ) = 1o2 vb S vb .
.EN
Clearly, the empty set is special. Application of
Lemma 3.14.3 to pairs of nonadjacent points in
$GAM sub {<= 2} ( gam )$ yields the following facts
(here distinct Latin letters denote distinct
indices taken from $"{"0 , ... , n "}"$).
.IP S1.
If $del mo GAM sub 2 ( gam )$ then
$S ( del )$ is special.
.IP S2.
If $abcd$ is special then precisely $mu$ of the sets
$ab , ac , ad , bc , bd , cd$ are special.
.IP S3.
If $ab$ and $cd$ are special then precisely $mu$ of the
sets $empty , ac , ad , bc , bd , abcd$
are special.
.IP S4.
If $abcd$ and $de$ are special then none or $mu$
of the sets $ad , bd , cd , abde , acde , bcde$ are
special.
.LP
(Indeed, if $abcd$ and $de$ represent vertices at distance two,
then they have $mu$ common neighbours, and these must be among
the six sets listed. On the other hand, if one of these six sets
is special, we must show that it represents a common neighbour
of $abcd$ and $de$. But this follows immediately from
Lemma 3.14.9.)
.LP
By definition, the edges of $DELTA$ are just the
special 2-sets. Since $mu >= 3$, S3 implies
that $DELTA$ has no subgraph consisting of two disjoint
edges. Therefore $DELTA$ consists of a connected graph
$DELTA sub 0$ and a (possibly empty) set of isolated
vertices. S3 implies
.IP S5.
Any two disjoint edges of $DELTA$ have
$mu - 1$ or $mu - 2$ transversals
(i.e. edges meeting both given edges).
.Xx "transversal of two edges"
.LP
Moreover, since $GAM$ is regular and not complete,
$GAM ( gam )$ is not complete; therefore we have
.IP S6.
$DELTA sub 0$ is not isomorphic to
$K sub 3$ or $K sub {s , 1}$.
.LP
We now consider each value of $mu$
separately. Clearly, S3 implies that
$mu <= 6$.
.SC Case 1:
$mu = 6$. By S1 and S2, a point of
$GAM sub 2 ( gam )$ is a complete
subgraph $K sub 4$ of $DELTA sub 0$.
Let $K$ be a complete subgraph $K sub m$ of
$DELTA sub 0$ with maximal $m >= 4$. If
$DELTA sub 0 != K$ then there is a vertex
$b mo DELTA sub 0$ at distance 1 from $K$, and
a vertex $a mo K$ adjacent with $b$. By
maximality of $K$, there is a vertex $c mo K$
with $c nadj b$. Let $d mo K minus "{"a , c "}"$.
Then the edges $ab, cd$ have at most 3 transversals,
contradicting S5. Hence $DELTA sub 0 = K$ is
complete and $GAM ( gam ) isom T(m)$.
By Proposition 3.14.10 this determines the representation
uniquely, and we find that $GAM$ is the halved $m$-cube.
.SC Case 2:
$mu = 5$. By S1 and S2, a point of
$GAM sub 2 ( gam )$ is a subgraph
$K sub {2,1,1}$ of $DELTA sub 0$.
Let $K$ be a subgraph of $DELTA sub 0$ isomorphic
to $K sub {m,1, ... ,1}$ with a
maximal number $m +s$ of vertices,
$m >= 2$, $s >= 2$. Using S5 we find as before
that $DELTA sub 0 = K sub {m ,1, ... ,1}$.
Let $L$ be the $m$-coclique of $DELTA sub 0$.
If $s > 2$, then we find that, for
$a, b, e mo K minus L$ and
$c , d mo L$, the set $abcd$ is special. Now
S4 gives a contradiction.
Hence $DELTA sub 0 = K sub m,1,1$, and we find by
Proposition 3.14.10 that $GAM isom K sub 1 ds T(m+2)$,
but this graph is not regular.
.SC Case 3:
$mu = 4$. By S5, each pair of disjoint edges has 2 or 3
transversals. By S1 and S2, a point of
$GAM sub 2 ( gam )$ is a special 4-set on
which $DELTA sub 0$ induces
.KS
[diagram]
.KE
and by S3, all subgraphs of $DELTA sub 0$ of these
shapes are special 4-sets.
.br
These subgraphs of $DEL sub 0$ are of the form $K sub 2,2$ and
$K sub 1,3 + roman { edge }$.
Let $E = A dotcu B$ be a largest subset of $DEL sub 0$
such that $a adj b$ for all $a mo A$ and $b mo B$,
where $A$ and $B$ are nonempty.
.br
(i)
.I
$E$ contains all vertices of $DEL sub 0$.
.R
Indeed, if not then let $c mo DEL sub 0$, $c nm E$.
We may assume $d(c,E) = 1$, say $c adj a mo A$.
By maximality of $E$ there is a $b mo B$ such that $b nadj c$.
Put $A sub 0 := A ca DEL (c)$ and $A sub 1 := A minus DEL (c)$,
then for any $a mo A sub 0$ and $d mo A sub 1$
we have $a adj d$ since $a c$ and $b d$ have at least two transversals.
But then $E cu "{" c "}" = A sub 0 dotcu (A sub 1 cu B cu "{" c "}" )$
is a larger subset of $DEL$ with the required property, contradiction.
.LP
(ii)
.I
$DEL sub 0$ does not contain a complete graph $K sub 4$ or a wheel
$K sub 1,2,2$.
.R
Indeed, two disjoint edges in a $K sub 4$ have 4 transversals, which is
impossible.
If $DEL sub 0$ contains an induced subgraph $K sub 2,2,1$, say
$a adj b adj c adj d adj a$, $e adj a,b,c,d$,
then $abcd$ is special, and by S4 we find a contradiction.
.LP
(iii)
.I
$DEL sub 0$ is either complete bipartite or complete bipartite with
one additional edge.
.R
Indeed, if $A$ contains two disjoint edges, then (since these must have
at least two transversals) $A$ contains a triangle or a quadrangle,
and since $B != empty$ this is forbidden by (ii).
Thus, all edges in $A$ pass through one vertex $d$.
If both $A$ and $B$ contain an edge then $DEL sub 0$ contains
a $K sub 4$. So we may assume that $B$ is a coclique.
If $vb B vb >= 2$ and $A$ contains two intersecting edges, then
$DEL sub 0$ contains a $K sub 1,2,2$, contradiction.
So we may assume that $B = "{"b"}"$.
If $A$ has no isolated point, then we can move $d$ from $A$
to $B$ and are done. So we may assume that $A$ has at least two
edges $c d$ and $d e$ and an isolated point $a$. Now S4
yields a contradiction.
.LP
(iv)
.I
If $DEL sub 0$ is complete bipartite, say $K sub s,t$,
then $GAM isom J(s+t,t)$.
.R
Indeed, this follows from Proposition 3.14.10.
.LP
Now assume that $DEL sub 0$ is a complete bipartite graph
$K sub s,t$ with one additional edge in the $t$-coclique,
so that $GAM ( gam )$ is a grid $s times t$
with one additional vertex adjacent to a
$s times 2$ subgrid. Let us temporarily call this latter
graph $s sub "\(pl" times t$ - in
the figure below the graph $3 sub "\(pl" times 4$ is drawn;
a label $ij$ denotes the vector $u = e sub i + e sub j$.
.KS
[diagram]
.KE
.LP
(v)
.I
If $GAM ( gam ) isom s sub "\(pl" times t$, then
$t = s+1$, and $GAM isom B(s)$.
.R
Indeed, with Proposition 3.14.10 we find that
$GAM isom B(s+t-2,s)$, and then regularity of $GAM$ implies $t = s+1$.
.SC Case 4:
$mu = 3$. By S5, each pair of disjoint edges
has 1 or 2 transversals. By S1 and S2, a point of
$GAM sub 2 ( gam )$ is a special 4-set on which
$DELTA sub 0$ induces
.KS
[diagram]
.KE
.LP
Assume first that $DELTA sub 0$ contains an induced path P
of length 3 with vertices $a adj b adj c adj d$.
By S3, $abcd$ is special. Let $e$ be at distance 1
from P. If $e adj d$, then S4 implies that
precisely two of the sets $abde, acde, bcde$ are special.
However, this is impossible: If $e adj a$, then
$e adj b$ implies that $abde, bcde$ are not special.
So $e nadj b$, and by symmetry $e nadj c$. But then
$abde, acde$ and $bcde$ are all special, contradiction.
And if $e nadj a$ then $e adj b$ since $ab$ and $de$ must
have a transversal, and $e nadj c$ since $bc$ and
$de$ cannot have 3 transversals. But then
$acde$ and $bcde$ are not special, contradiction.
Hence $e nadj d$, and by symmetry, $e nadj a$.
.br
If $e adj b$ and $e adj c$, then S4 with $( b , d )$
interchanged gives a contradiction. Therefore $e$ is adjacent
to just one of $b$ and $c$
(and if $e adj b$ then $ebcd$ is special). Hence the neighbours
$!= c$ of $b$ form a coclique $A$, and the
neighbours $!= b$ of $c$ form a coclique $D$.
Now it is easy to see that
$DELTA sub 0 = A cu "{" b , c "}" cu D$
(the coclique extension of $P$ where $a$ and $d$ are blown up to
$A$ and $D$, respectively).
Since $gam$ has valency
$vb A vb + vb D vb + 1$ and $bc$ has
$X>= vb A vb + vb D vb + 2$ neighbours
$gam$, $ab$ $( a mo A )$, $cd$ $(d mo D )$ and $P$,
this contradicts the regularity of $GAM$. Therefore
$DELTA sub 0$ does not contain an induced path of length 3.
.br
[If we do not assume regularity, this case leads to
$GAM isom K sub 1 ds K sub { vb A vb + 1 , vb D vb + 1 }$.]
.LP
Now if $GAM sub 2 ( gam )$
contains a vertex $abcd$ with
$b adj c adj d adj b$ and $e$ is adjacent
with $d$, then $abcd$ and $de$ have only two common
neighbours, contradiction.
Hence $e nadj d$ and by symmetry,
$e nadj b , c$. Therefore $bcd$ is an
isolated triangle,
$DELTA sub 0 = "{" b , c , d "}"$, contradicting S6.
This shows that $GAM sub 2 ( gam )$ contains only special
4-sets forming a 3-claw.
[If we do not assume regularity, this case leads to $GAM isom L(s,t)$,
where $L(s,t)$ is the graph represented by
$e sub i$ ($1 <= i <= 3s+t$), $e sub 3j-2 + e sub 3j-1 + e sub 3j$
($1 <= j <= s$).]
.LP
Let $abcd$ be such a special 4-set, $a adj b, c, d$.
If $e adj d$ then $e adj b, c$ since
$DELTA sub 0$ has no path of length 3; but
then S4 is violated. Hence $b, c, d$ are vertices of
$DELTA sub 0$ of valency 1, and
since $DELTA sub 0$ is connected and
has no path of length 3, every vertex
$!= a$ of $DELTA sub 0$ must be adjacent to $a$. By S6,
$DELTA sub 0$ contains at least one further edge
$ef$. If there is another edge
$eg$ (or $fg$), then $ag,ef$ have 3
transversals, contradicting S5,
and if there is another edge $gh$ then
$ef,gh$ have no transversal, again contradicting S5.
Therefore there is no further edge.
Now $ef$ must have a neighbour in $GAM sub 2 ( gam )$, but
there is no special 4-set containing $ef$, contradiction.
Therefore $mu = 3$ is impossible.
[If we do not assume regularity, then we find $GAM isom L(s,t)$ again.]
.LP
This completes the proof of the theorem.
.Eop
$Re$.
.SC Koolen
.[[
Koolen master's thesis 1990
.]]
generalized this theorem by omitting `regular' from the assumptions.
In the proof above we mentioned which further graphs arise in this
more general situation.
.bp
Tables of parameter sets for bipartite (but not antipodal) distance-regular
graphs with $v <= 4096$ that pass all known existence tests.
.LP
.Zh "Diameter 4 - Bipartite (but not antipodal) graphs"
.br
.Small
These graphs are precisely the incidence graphs of partial $lambda$-geometries
with nexus $e < k-1$ (i.e., excluding the symmetric nets),
cf. Theorem 1.7.1.
Apart from the families of generalized octagons of order $(1,t)$
(i.e., incidence graphs of generalized quadrangles of order $(t,t)$),
and (pseudo) $D sub m (q)$ graphs, an infinite family of
feasible $Q$-polynomial parameter sets with
$k = 3 Binom(m,3) + Binom(m-1,2)$, $c sub 2 = Binom(m,2) - 1$,
$c sub 3 = 3 Binom(m,3)$, $q sub 33 sup 3 = p sub 44 sup 4 = 0$
is visible. Such a graph is known only for $m = 4$ (and for $m = 3$
we get the 4-cube, which is antipodal).
.nr aA \w'+ $v = 0000 = 1 + 000 + 000 + 0000 + 0000$'
.de Bx
.na
.ti -10n
.ds B; "
.ie \\w'\\*(Bs'u+\\w'\\*(Ba'u-\\n(.lu+\\n(aAu+1n \{.ta \\n(.luR
\\&\\*(Bk \\*(Bv \\*(Ba
.br
.ie \\w'\\*(Bs'u+\\w'\\*(Bp'u+\\n(aAu-\\n(.lu+1n \{.ta \\n(.lu-10nR
\\*(Bs \\*(Bp\}
.el \{.ta \\n(aAu-10nL \\n(.lu-10nR
.ie \\n(aAu-12n-\\w'\\*(Bn'u-\\w'\\*(Bc'u \{\c
.if !'\\*(Bn'' .if !'\\*(Bc'' .as Bn ";
.as Bn \\*(Bc
\\*(Bn \\*(Bs \\*(Bp
.rm Bn Bc\}
.el \{\c
\\*(Bs \\*(Bp\}\}
.br
.if !'\\*(Bn'' \\*(Bn\c
.if !'\\*(Bc'' .if !'\\*(Bn'' ;
.if !'\\*(Bc'' \\*(Bc\}
.el \{.ta \\n(aAuL \\n(.luR
\\&\\*(Bk \\*(Bv \\*(Bs \\*(Ba
.br
.if !'\\*(Bp'' .if !'\\*(Bn'' .as Bn ";
.as Bn \\*(Bp
.if !'\\*(Bc'' .if !'\\*(Bn'' .as Bn ";
.as Bn \\*(Bc
.if !'\\*(Bn'' \\*(Bn\}
.br
..
.in 10n
.so oo/IA4B.out
.in 0
.ad n
.Big