\documentstyle[a4,12pt]{article}
\newcommand{\Ff}{{\bf F}}
\newcommand{\isom}{\,\simeq\,}

\title{A new distance-regular graph associated to the Mathieu group $M_{10}$}
\author{A.E. Brouwer, J.H. Koolen \& R.J. Riebeek}
\begin{document}
\maketitle

\begin{abstract}
We construct a bipartite distance-regular graph with intersection array
$\{ 45,44,36,5; 1,9,40,45 \}$ and automorphism group $3^5:(2 \times M_{10})$
(acting edge-transitively)
and discuss its relation to previously known combinatorial structures.
\end{abstract}

\section{Introduction}
Let $G$ be the perfect ternary Golay code generated by the rows of the
circulant $(-+-+++---+-)_{11}$. Then $G$ is a ternary $[11,6,5]$ code.
Let $\Gamma$ be the coset graph of $G$, that is, the graph with
as vertices the $3^5$ cosets of $G$ in $\Ff_3^{11}$, where two cosets
are adjacent when their difference contains a vector of weight one.
Then $\Gamma$ is a strongly regular graph with parameters
$(v,k,\lambda,\mu) = (243,22,1,2)$, known as the Berlekamp-van\,Lint-Seidel
graph. (See Berlekamp, van Lint \& Seidel \cite{BvLS}, and
Brouwer, Cohen \& Neumaier \cite{BCN}, Section 11.3B.)

In \cite{BCN}, p. 360, the question was raised whether the
complementary graph of the graph $\Gamma$
is the halved graph of a bipartite distance-regular graph $\Delta$
of diameter 4. In this note this question is answered affirmatively:
the last two authors constructed such a graph $\Delta$.
(This also settles the last open case in Riebeek \cite{R}, Chapter 7.)

\section{Construction}
Put $Q := \{1,3,4,5,9\}$, the set of (nonzero) squares
mod 11, and $N := \{2,6,7,8,10\}$, the nonsquares.
Consider in the graph $\Gamma$ the set $D$ consisting of the following
45 cosets (we write $u$ instead of $u + G$):
$$e_j , ~~ - e_0 - e_j ~ (j \in N)$$
$$e_0 - e_i, ~~ e_i + e_{3i},~~ \pm(e_i - e_{9i}),~~
e_i - e_{7i},~~ - e_i - e_{6i},~~ - e_i - e_{10i} ~ (i \in Q).$$
Then $D$ is a 45-coclique, and the point-coclique incidence graph $\Delta$
on cosets and translates of $D$ is distance-regular with intersection array
$\{ 45,44,36,5;$ $1,9,40,45 \}$ and distance distribution diagram

{\scriptsize

$$\begin{picture}(300,30)(0,-16)
\put(0,0){\circle{20}}\put(0,0){\makebox(0,0){1}}
\put(10,0){\line(1,0){40}}
\put(13,-8){\makebox(0,0)[l]{45}}
\put(47,-8){\makebox(0,0)[r]{1}}
\put(60,0){\circle{20}}\put(60,0){\makebox(0,0){45}}
\put(60,-15){\makebox(0,0){-}}
\put(70,0){\line(1,0){40}}
\put(73,-8){\makebox(0,0)[l]{44}}
\put(107,-8){\makebox(0,0)[r]{9}}
\put(120,0){\circle{20}}\put(120,0){\makebox(0,0){220}}
\put(120,-15){\makebox(0,0){-}}
\put(130,0){\line(1,0){40}}
\put(133,-8){\makebox(0,0)[l]{36}}
\put(167,-8){\makebox(0,0)[r]{40}}
\put(180,0){\circle{20}}\put(180,0){\makebox(0,0){198}}
\put(180,-15){\makebox(0,0){-}}
\put(190,0){\line(1,0){40}}
\put(193,-8){\makebox(0,0)[l]{5}}
\put(227,-8){\makebox(0,0)[r]{45}}
\put(240,0){\circle{20}}\put(240,0){\makebox(0,0){22}}
\put(240,-15){\makebox(0,0){-}}
\put(300,0){\makebox(0,0){\normalsize $v=486$.}}
\end{picture}$$
}
The automorphism group of $\Delta$ has shape $3^5:(2 \times M_{10})$,
and acts edge-transitively with point stabilizer isomorphic to $M_{10}$.
The orbit diagram is

{\scriptsize

$$\begin{picture}(300,150)(0,-76)
\put(0,0){\circle{20}}\put(0,0){\makebox(0,0){1}}
\put(60,0){\circle{20}}\put(60,0){\makebox(0,0){45}}
\put(120,30){\circle{20}}\put(120,30){\makebox(0,0){40}}
\put(120,-30){\circle{20}}\put(120,-30){\makebox(0,0){180}}
\put(180,60){\circle{20}}\put(180,60){\makebox(0,0){90}}
\put(180,0){\circle{20}}\put(180,0){\makebox(0,0){36}}
\put(180,-60){\circle{20}}\put(180,-60){\makebox(0,0){72}}
\put(240,30){\circle{20}}\put(240,30){\makebox(0,0){2}}
\put(240,-30){\circle{20}}\put(240,-30){\makebox(0,0){20}}
\put(10.000,0.000){\line(1,0){40.000}}
\put(13.000,-8.000){\makebox(0,0)[l]{45}}
\put(47.000,-8.000){\makebox(0,0)[r]{1}}
\put(68.944,4.472){\line(2,1){42.111}}
\put(68.944,12.472){\makebox(0,0)[c]{8}}
\put(108.056,28.528){\makebox(0,0)[r]{9}}
\put(68.944,-4.472){\line(2,-1){42.111}}
\put(68.944,-12.472){\makebox(0,0)[c]{36}}
\put(108.056,-28.528){\makebox(0,0)[r]{9}}
\put(128.944,34.472){\line(2,1){42.111}}
\put(128.944,42.472){\makebox(0,0)[c]{9}}
\put(168.056,58.528){\makebox(0,0)[r]{4}}
\put(128.944,25.528){\line(2,-1){42.111}}
\put(131.944,28.528){\makebox(0,0)[l]{9}}
\put(171.056,12.472){\makebox(0,0)[c]{10}}
\put(125.547,21.679){\line(2,-3){48.906}}
\put(125.547,13.679){\makebox(0,0)[c]{18}}
\put(171.453,-49.679){\makebox(0,0)[r]{10}}
\put(125.547,-21.679){\line(2,3){48.906}}
\put(125.547,-13.679){\makebox(0,0)[c]{18}}
\put(171.453,49.679){\makebox(0,0)[r]{36}}
\put(128.944,-25.528){\line(2,1){42.111}}
\put(131.944,-28.528){\makebox(0,0)[l]{6}}
\put(171.056,-12.472){\makebox(0,0)[c]{30}}
\put(128.944,-34.472){\line(2,-1){42.111}}
\put(128.944,-42.472){\makebox(0,0)[c]{12}}
\put(168.056,-58.528){\makebox(0,0)[r]{30}}
\put(188.944,55.528){\line(2,-1){42.111}}
\put(191.944,58.528){\makebox(0,0)[l]{1}}
\put(231.056,42.472){\makebox(0,0)[c]{45}}
\put(185.547,51.679){\line(2,-3){48.906}}
\put(185.547,43.679){\makebox(0,0)[c]{4}}
\put(231.453,-19.679){\makebox(0,0)[r]{18}}
\put(188.944,-4.472){\line(2,-1){42.111}}
\put(188.944,-12.472){\makebox(0,0)[c]{5}}
\put(228.056,-28.528){\makebox(0,0)[r]{9}}
\put(188.944,-55.528){\line(2,1){42.111}}
\put(191.944,-58.528){\makebox(0,0)[l]{5}}
\put(231.056,-42.472){\makebox(0,0)[c]{18}}
\put(300,0){\makebox(0,0){\normalsize $v=486$.}}
\end{picture}$$
}
\section{Structure of the group; related graphs}
In order to describe the group of automorphisms more
precisely, we have to specify the representation of
$2 \times M_{10}$ inside $GL(5,3)$. The direct factor $2$
may be represented by $\pm I$, and then it remains to look at
the group $H := 3^5 : M_{10}$, the stabilizer of the bipartition
of $\Delta$. This group has a centre of order 3, acting fixpoint freely
on $\Delta$. The quotient graph is a bipartite graph $E$ of valency 45
on 162 vertices that can be found inside the McLaughlin graph $\Lambda$
as follows.

Let $x$, $y$ be two adjacent vertices of $\Lambda$.
Let $X$ and $Y$ be the sets of vertices of $\Lambda$ adjacent
to $x$ but not to $y$, and to $y$ but not to $x$, respectively.
Then $|X| = |Y| = 81$ and $E$ is isomorphic to the graph
with vertex set $X \cup Y$, where $X$ and $Y$ are cocliques,
and the edges between $X$ and $Y$ are precisely those present in $\Lambda$.
(Thus, $E$ is not the graph induced by $X \cup Y$; in $\Lambda$
the sets $X$ and $Y$ induce subgraphs of valency 20.
See also Brouwer \& Haemers \cite{BH}, Construction D.)

{\scriptsize

$$\begin{picture}(280,90)(-30,-50)
\put(-40,50){\makebox(0,0)[c]{\normalsize $\Lambda$:}}
\put(-16,30){\makebox(0,0)[r]{\normalsize $x$:}}
\put(-16,-30){\makebox(0,0)[r]{\normalsize $y$:}}
\put(0,30){\circle{20}}\put(0,30){\makebox(0,0){1}}
\put(0,-30){\circle{20}}\put(0,-30){\makebox(0,0){1}}
\put(60,0){\circle{20}}\put(60,0){\makebox(0,0){30}}
\put(120,30){\circle{20}}\put(120,30){\makebox(0,0){81}}
\put(120,-30){\circle{20}}\put(120,-30){\makebox(0,0){81}}
\put(180,0){\circle{20}}\put(180,0){\makebox(0,0){81}}
\put(0,-20){\line(0,1){40}}
\put(3,-15){\makebox(0,0)[l]{1}}
\put(3,15){\makebox(0,0)[l]{1}}
\put(8.944,25.528){\line(2,-1){42.111}}
\put(11.944,25){\makebox(0,0)[l]{30}}
\put(51.056,12.472){\makebox(0,0)[c]{1}}
\put(10,30){\line(1,0){100}}
\put(13,38){\makebox(0,0)[l]{81}}
\put(107,38){\makebox(0,0)[r]{1}}
\put(8.944,-25.528){\line(2,1){42.111}}
\put(11.944,-25){\makebox(0,0)[l]{30}}
\put(51.056,-12.472){\makebox(0,0)[c]{1}}
\put(10,-30){\line(1,0){100}}
\put(13,-38){\makebox(0,0)[l]{81}}
\put(107,-38){\makebox(0,0)[r]{1}}
\put(60,-18){\makebox(0,0){2}}
\put(68.944,4.472){\line(2,1){42.111}}
\put(68.944,12.472){\makebox(0,0)[c]{27}}
\put(108.056,25){\makebox(0,0)[r]{10}}
\put(68.944,-4.472){\line(2,-1){42.111}}
\put(68.944,-12.472){\makebox(0,0)[c]{27}}
\put(108.056,-25){\makebox(0,0)[r]{10}}
\put(70,0){\line(1,0){100}}
\put(73,4){\makebox(0,0)[l]{54}}
\put(167,4){\makebox(0,0)[r]{20}}
\put(120,48){\makebox(0,0){20}}
\put(120,-20){\line(0,1){40}}
\put(123,-15){\makebox(0,0)[l]{45}}
\put(123,15){\makebox(0,0)[l]{45}}
\put(128.944,25.528){\line(2,-1){42.111}}
\put(131.944,28.528){\makebox(0,0)[l]{36}}
\put(171.056,12.472){\makebox(0,0)[c]{36}}
\put(120,-48){\makebox(0,0){20}}
\put(128.944,-25.528){\line(2,1){42.111}}
\put(131.944,-28.528){\makebox(0,0)[l]{36}}
\put(171.056,-12.472){\makebox(0,0)[c]{36}}
\put(198,0){\makebox(0,0){20}}
\put(240,0){\makebox(0,0){\normalsize $v=275$.}}
\end{picture}$$
}

\medskip
{\bf A larger graph.}
Let $Z$ be the set of 81 vertices in $\Lambda$ nonadjacent to
both $x$ and $y$. The graph induced by $\Lambda$ on
$X \cup Y \cup Z$, after switching with respect to $Z$,
is isomorphic to the Delsarte graph, a strongly regular
graph with parameters $(v,k,\lambda,\mu) = (243,110,37,60)$.
If we remove from this graph the edges inside $X$, $Y$ or $Z$,
we obtain a tripartite graph $F$ of valency 90 on 243 vertices
such that the subgraph induced on the union of any two of its parts
is isomorphic to $E$. We have ${\rm Aut} (F) \isom 3^5 : (2 \times M_{10})$.

This latter graph has a triple cover $\Sigma$, of course again
tripartite, such that the subgraph induced on the union of any two
of its parts is isomorphic to $\Delta$.
We have ${\rm Aut} (\Sigma) \isom 3^6 : (2 \times M_{10})$.

The graph $\Sigma$ can be constructed as follows:

Let $A := \left(\begin{array}{cccccc}
1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 \\
2 & 2 & 2 & 0 & 0 & 0 \\
2 & 2 & 1 & 1 & 0 & 0 \\
0 & 1 & 2 & 1 & 2 & 0 \\
1 & 1 & 2 & 0 & 0 & 1
\end{array} \right)$
and $B := \left(\begin{array}{cccccc}
1 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 & 2 & 0 \\
0 & 2 & 0 & 2 & 2 & 0 \\
2 & 0 & 0 & 1 & 1 & 0 \\
0 & 1 & 2 & 0 & 1 & 0 \\
1 & 1 & 1 & 0 & 0 & 2
\end{array} \right)$.
Let $M := \langle A,B \rangle$ be the group generated by $A$ and $B$.
Then $M \isom M_{10}$, and $M$ has orbits of sizes 1, 1, 1, 20, 20, 20,
72, 72, 72, 90, 90, 90, 180 on $\Ff_3^6$.
Let $N := \langle A,B,-I \rangle$. Then $N \isom 2 \times M_{10}$,
and $N$ has orbits of sizes 1, 2, 20, 40, 72, 144, 90, 180, 180.
The vector $(000001)$ is a representative of the $N$-orbit $O$ of size 90.
The graph $\Sigma$ is the graph with vertex set $\Ff_3^6$, where
two vertices are adjacent when their difference lies in $O$.
Now the graph $\Delta$ is the subgraph of $\Sigma$ induced on the
set of vectors with nonzero last coordinate.

\section{Acknowledgements}
Hans Cuypers suggested that ${\rm Aut} (\Delta)$ might be related to
the edge stabilizer of the McLaughlin graph $\Lambda$.
The availability of the computer algebra systems GAP \cite{G},
GRAPE \cite{S} and Nauty \cite{McK} has been very useful.


\begin{thebibliography}{}

\bibitem[BvLS]{BvLS} E.R. Berlekamp, J.H. van Lint \& J.J. Seidel,
{\it A strongly regular graph derived from the perfect ternary Golay code},
pp. 25-30 in: A survey of combinatorial theory, Symp. Colorado State Univ., 1971,
J.N. Srivastava et al., eds., North Holland, 1973.

\bibitem[BCN]{BCN} A.E. Brouwer, A.M. Cohen \& A. Neumaier,
{\it Distance-regular graphs\/}, Springer, Heidelberg, 1989.

\bibitem[BH]{BH} A.E. Brouwer \& W.H. Haemers,
{\it Structure and uniqueness of the (81,20,1,6) strongly regular graph\/},
Discrete Math. 106/107 (1992) 77-82.

\bibitem[G]{G} M. Sch\"onert et al.,
{\it GAP: Groups, Algorithms and Programming\/},
Aachen, April 1992.

\bibitem[McK]{McK} B.D. McKay,
{\it Nauty users guide (version 1.5)\/},
Technical Report TR-CS-90-02, Computer Science Department,
Australian National University, 1990.

\bibitem[R]{R} R.J. Riebeek,
{\it Halved graphs of distance-regular graphs\/},
Master's thesis, Eindhoven Univ. of Techn., June 1992.

\bibitem[S]{S} L.H. Soicher,
{\it GRAPE: a system for computing with graphs and groups\/},
in: Proc. 1991 DIMACS Workshop on Groups and Computation, 
DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 
to appear.

\end{thebibliography}

\end{document}
