UDC 519.95

MATHEMATICS

G. M. ADELSON-VELSKII, B. Yu. WEISFEILER,
A. A. LEMAN, I. A. FARADZHEV

ON AN EXAMPLE OF A GRAPH HAVING NO TRANSITIVE AUTOMORPHISM GROUP

(Presented by Academician P. S. Novikov on 29 VII 1968)

1. In paper \((^1)\) a construction was indicated which makes it possible, for a given graph \(\Gamma\), to construct in an invariant way the matrix algebra \(\mathfrak A(\Gamma)\). In the present paper we consider graphs to which there corresponds a special class of algebras—cells.

An a priori definition of a cell:

A matrix algebra \(\mathfrak A\) is called a cell if it has the following properties:

1. \(\mathfrak A\) is invariant under transposition.

2. In \(\mathfrak A\) there exists a basis \(e_0=E, e_1,\ldots,e_k\) such that \(e_i\) is a matrix consisting of zeros and ones and having \(n_i\) ones in each row and each column,

\[ n=\sum_{i=1}^{k} n_i+1;\qquad \sum_{i=}^k e_i \]

is a matrix all of whose entries are equal to 1.

Let \(\Gamma\) be a graph and \(\mathfrak A(\Gamma)\) its algebra. The condition that \(\mathfrak A(\Gamma)\) is a cell has the following geometric meaning. To each ordered sequence \((g_0,g_1,\ldots,g_m)\) of vertices of the graph \(\Gamma\) \((m\geqslant 1)\) there corresponds the sequence \((\xi_1,\ldots,\xi_m)\), where \(\xi_i=1\) if \((g_{i-1},g_i)\) is an edge of \(\Gamma\), and \(\xi_i=0\) otherwise. If \(\mathfrak A(\Gamma)\) is a cell, then for any fixed sequence \(\Xi_0=(\xi_1,\ldots,\xi_k)\) of zeros and ones the number of sequences of vertices \((g\ldots)\) and \((h\ldots)\) to which the sequence \(\Xi_0\) corresponds is the same for any two vertices \(g\) and \(h\).

II. In \((^1)\) the following was stated.

Hypothesis. The automorphism group \(\operatorname{Aut}\Gamma\) of a graph \(\Gamma\), the algebra \(\mathfrak A(\Gamma)\) of which is a cell, is transitive on its vertices.

Below a counterexample to this hypothesis is constructed.

A. Let \(\Gamma\) be a graph, \(G=\operatorname{Aut}\Gamma\), and \(\mathfrak Z(G)\) the algebra of matrices commuting with the group \(G\). \(\mathfrak Z(G)\) has a basis \(f_i,\ i\in\mathfrak I\), all of whose matrices consist of 0 and 1. It is known that \(\mathfrak A(\Gamma)\) is a subalgebra of \(\mathfrak Z(G)\), and

\[ e_i=\sum_{j\in\mathfrak I_i} f_j, \]

where the \(\mathfrak I_i\) are suitable disjoint subsets of the set \(\mathfrak I\).

B. If \(n=2p\), \(p\) is prime, and \(G\) is a primitive group, transitive but not doubly transitive on the vertices of the graph \(\Gamma\) (with \(n\) vertices), then, as shown in \((^2)\), \(\dim \mathfrak Z(G)=3\), \(2p=m^2+1\), \(n_1=m(m+1)/2\), \(n_2=m(m-1)/2\). Hence, and from what was said above, it follows that \(\dim\mathfrak A(\Gamma)\leqslant 3\); the case \(\dim\mathfrak A(\Gamma)=2\) is trivial and corresponds to the complete graph \(\Gamma\). Therefore we shall assume that \(\mathfrak A(\Gamma)=\mathfrak Z(G)\). Note that the matrices \(e_i\) in this case are symmetric and are, therefore, adjacency matrices of undirected graphs without multiple edges. Moreover, \(\mathfrak A(e_i)=\mathfrak Z(G)\), \(i>0\).

As was indicated in \((^2)\), and also in a later paper \((^3)\), it is unknown whether there exists a primitive not doubly transitive group \(G\) for \(p>5\).

C. For \(p=13\) all three-dimensional cells were constructed whose automorphism group contains the element \(\sigma=(1,2,\ldots,p)(p+1,\ldots,2p)\).

It turned out that the automorphism groups of all the corresponding graphs are intransitive. Hence, and from the results of [2], it follows that

Every primitive transitive permutation group of degree 26 is doubly transitive.

III. In view of IIA, the basic matrix of the \(e_1\)-cell, permutable with \(\sigma\), has the form
\[ \begin{pmatrix} A_1 A_2\\ A_3 A_4 \end{pmatrix}, \]
where \(A_3'=A_2,\ A_1'=A_1,\ A_4'=A_4,\ A_i=\sum_{j\in\mathfrak S_i}\tau^j\), where \(\tau\) is the permutation matrix of \((0,1,\ldots,p-1)\), and \(\mathfrak S_i\) are suitable subsets of residues \(\bmod\, p\); \(\mathfrak S_1\) and \(\mathfrak S_4\) do not contain 0.

The choice of the suitable sets \(\mathfrak S_i\) was carried out by direct search with the aid of a computer. In all, 104 different collections of \(\mathfrak S_i\) were obtained. In all cases either
\[ \mathfrak S_1=\{1,3,4,9,10,12\},\quad \mathfrak S_4=\{2,5,6,7,8,11\}, \]
or conversely; for fixed \(\mathfrak S_2\) these two cases are, evidently, isomorphic. For given \(\mathfrak S_1\) and \(\mathfrak S_4\), 52 collections of \(\mathfrak S_2\) were obtained; the corresponding graphs are pairwise isomorphic. The isomorphisms consist of permutations belonging to the group generated by the substitutions
\[ \begin{pmatrix} E&0\\ 0&\tau \end{pmatrix} \quad\text{and}\quad \begin{pmatrix} 0&\rho\\ \rho^{-1}&0 \end{pmatrix} \]
for
\[ \rho=(0)(1,2,4,8,3,6,12,11,9,5,10,7); \]
one of the admissible collections is
\[ \mathfrak S_2=\{0,1,3,9\}. \]
The intransitivity of the obtained graph \(\Gamma\) is established by comparing the subgraphs \(\Gamma_1\) and \(\Gamma_2\), spanned by the vertices adjacent respectively to the 1st and 14th vertices of the graph \(\Gamma\) (Fig. 1).

Fig. 1

Received
5 VI 1968

REFERENCES

1. B. Yu. Weisfeiler, L. L. Leman, Scientific and Technical Information, No. 9, issue 2 (1968).
2. H. Wielandt, Math. Zs., 63, 478 (1955).
3. D. G. Higman, Math. Zs., 86, No. 2, 145 (1964).