% A LaTeX file for a 3 page document
\documentstyle[a4,12pt]{article} \font\twlrm=cmr12 \font\twlbf=cmbx12
\def \im {\cong} \def \cl {\centerline} \def \ss {\smallskip} \def \ms
{\medskip} \def \bs {\bigskip} \def \ds {\displaystyle} \def \split
{\colon} \def \bec {\colon=} \def \ns {{}^{\ds .}} \def \intersect
{\cap} \def \union {\cup} \def \la {\langle} \def \ra {\rangle} \def \x
{\times} \def \a {\alpha} \def \b {\beta} \def \G {\Gamma} \def \D
{\Delta} \def \S {\Sigma} \def \s {\sigma} \def \t {\tau} \def \w
{\omega} \def \O {\Omega} \def \Aut {{\rm Aut}}
\newtheorem{thm}{Theorem} \newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition} \newtheorem{cor}{Corollary}
\newtheorem{predefn}{Definition}
\newenvironment{defn}{\begin{predefn}\rm}{\end{predefn}}
\title{Yet another distance-regular graph related to a Golay code}
\author{
Leonard H. Soicher\\ School of Mathematical Sciences\\ Queen Mary and
Westfield College\\ Mile End Road, London E1 4NS, U.K.\\
email: L.H.Soicher@qmw.ac.uk}
\date{ }
\begin{document}
\maketitle
\begin{abstract} We describe a new distance-regular, but not
distance-transitive, graph. This graph has intersection array
$\{110,81,12;1,18,90\}$, and automorphism group $M_{22}\split2$.
\end{abstract}
In \cite{BCN}, Brouwer, Cohen and Neumaier discuss many distance-regular
graphs related to the famous Golay codes. In this note, we describe yet
another such graph.
Ivanov, Linton, Lux, Saxl and the author \cite{ILLSS} have
classified all primitive distance-transitive representations of the
sporadic simple groups and their automorphism groups. As part of this
work, all multiplicity-free primitive representations of
such groups have also been classified. One such representation is
$M_{22}\split2$ on the cosets of $L_2(11)\split2$. This representation
has rank 6, with subdegrees 1, 55, 55, 66, 165, 330. Let $\G$ be the
graph obtained by the edge-union of the orbital graphs corresponding to
the two suborbits of length 55. By examining the sum
$$\left(\begin{array}{rrrrrr} 0 & 55 & 0 & 0 & 0 & 0 \\ 1 & 8 & 4 & 0 &
18 & 24 \\ 0 & 4 & 12 & 0 & 3 & 36 \\ 0 & 0 & 0 & 10 & 10 & 35 \\ 0 & 6
& 1 & 4 & 20 & 24 \\ 0 & 4 & 6 & 7 & 12 & 26 \\ \end{array}\right)
\quad +\quad \left(\begin{array}{rrrrrr} 0 & 0 & 55 & 0 & 0 & 0 \\ 0 &
4 & 12 & 0 & 3 & 36 \\ 1 & 12 & 0 & 0 & 30 & 12 \\ 0 & 0 & 0 & 10 & 20
& 25 \\ 0 & 1 & 10 & 8 & 4 & 32 \\ 0 & 6 & 2 & 5 & 16 & 26 \\
\end{array}\right)$$ of the intersection matrices corresponding to
these two orbital graphs, we see that $\G$ is distance-regular, with
intersection array $$\{110,81,12;1,18,90\}.$$ According to \cite[p.430]{BCN},
this graph was previously unknown.
We now give a description of $\G$ in terms of a punctured
binary Golay code. This description was obtained using the
{\sf GRAPE} share library package \cite{GRAPE} of the {\sf GAP} system
\cite{GAP} (available from {\tt ftp.math.rwth-aachen.de}).
Let ${\cal C}_{22}$ be the code obtained by puncturing in one
co-ordinate the (non-extended) binary Golay code.
Then ${\cal C}_{22}$ is a $[22,12,6]$--code, with
automorphism group $M_{22}\split2$.
Let $M$ be the set of the 77 minimum weight non-zero
words of ${\cal C}_{22}$,
and $V$ be the set of the 672 unordered pairs of words of weight
11 which have disjoint support.
For $v=\{v_1,v_2\}\in V$ define $$M(v)\bec\{m\in M\mid
\hbox{weight$(v_1+m)$ $=$ weight$(v_2+m)$}\}.$$
We remark that $M(v)$ has size 55.
Now define $\G$ to have vertex set $V$, with vertices $v,w$ joined
by an edge if and only if $$|M(v)\cap M(w)|=43.$$
We use {\sf GRAPE} to check that $\G$ is indeed distance-regular, with
intersection array $\{110,81,12;1,18,90\}$.
Using {\em nauty} \cite{nauty} within {\sf GRAPE}, we determine
that $\Aut(\G)\im M_{22}\split2$, and so $\G$ is not distance-transitive.
Further computations reveal the following intriguing fact.
Let $v,w\in V$, $v\not=w$. Then in $\G$, we have
$$d(v,w)=i$$ if and only if $$|M(v)\cap M(w)|=47-4i.$$
As noted in \cite[p.430]{BCN}, the distance-2 graph $\G_2$
is strongly regular, and it has parameters
$$(v,k,\lambda,\mu)=(672,495,366,360).$$ Indeed, $\G_2$ is a rank
3 graph for $U_6(2)$ (illustrating $M_{22}\le U_6(2)$). The full automorphism
group of $\G_2$ is $U_6(2)\split S_3$.
It would be interesting to have a natural computer-free proof
of the results in this note, and to
see if these results generalize to other codes.
\medskip
\noindent {\bf Remark} A.A.~Ivanov has since informed me that about ten
years ago he and his colleagues in Moscow discovered the four class
association scheme associated with the graph $\G$ (see \cite{FKM,IKF}),
but they did not check this scheme to determine if it came from a
distance-regular graph.
\begin{thebibliography}{99}
\bibitem{BCN} A.E.~Brouwer, A.M.~Cohen and A.~Neumaier,
{\it Distance-Regular Graphs}, Springer, Berlin and New York, 1989.
\bibitem{FKM} I.A.~Faradzev, M.H.~Klin and M.E.~Muzichuk,
Cellular rings and groups of automorphisms of graphs,
in {\it Investigations in Algebraic Theory of Combinatorial Objects}
(I.A.~Faradzev, A.A.~Ivanov, M.H.~Klin and A.J.~Woldar, eds.),
Kluwer Academic Publishers, 1994, pp.~1--153.
\bibitem{IKF} A.A.~Ivanov, M.H.~Klin and I.A.~Faradzev,
Primitive representations of nonabelian
simple groups of order less than $10^6$, Part 2, Preprint, VNIISI,
Moscow, 1984.
\bibitem{ILLSS} A.A.~Ivanov, S.A.~Linton, K.~Lux, J.~Saxl and
L.H.~Soicher, Distance-transitive representations of the sporadic
groups, {\it Comm. Algebra}, to appear.
\bibitem{nauty} B.D.~McKay, {\em nauty} user's guide (version 1.5),
Technical report TR-CS-90-02, Computer Science Department, Australian
National University, 1990.
\bibitem{GAP} M.~Sch\"onert, et. al., {\sf GAP} -- Groups, Algorithms and
Programming, fourth edition, Lehrstuhl D f\"ur Mathematik, RWTH Aachen,
1994.
\bibitem{GRAPE} L.H.~Soicher, {\sf GRAPE}: a system for computing with
graphs and groups, in {\it Groups and Computation}, L.~Finkelstein and
W.M.~Kantor, eds., DIMACS Series in
Discrete Mathematics and Theoretical Computer Science {\bf 11}, A.M.S.,
1993, pp.~287--291.
\end{thebibliography}
\end{document}