> < ^ From:

^ Subject:

% 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}

> < [top]