Classification of distance-transitive orbital graphs of overgroups of the Jevons group

B. A. Pogorelov ; M. A. Pudovkina

Diskretnaya Matematika, Tome 30 (2018) no. 4, pp. 66-87.

Résumé

The Jevons group $A{\tilde S_n}$ is an isometry group of the Hamming metric on the $n$-dimensional vector space ${V_n}$ over $GF(2)$. It is generated by the group of all permutation $(n \times n)$-matrices over $GF(2)$ and the translation group on ${V_n}$. Earlier the authors of the present paper classified the submetrics of the Hamming metric on ${V_n}$ for $n \geqslant 4$, and all overgroups of $A{\tilde S_n}$ which are isometry groups of these overmetrics. In turn, each overgroup of $A{\tilde S_n}$ is known to define orbital graphs whose “natural” metrics are submetrics of the Hamming metric. The authors also described all distance-transitive orbital graphs of overgroups of the Jevons group $A{\tilde S_n}$. In the present paper we classify the distance-transitive orbital graphs of overgroups of the Jevons group. In particular, we show that some distance-transitive orbital graphs are isomorphic to the following classes: the complete graph ${K_{{2^n}}}$, the complete bipartite graph ${K_{{2^{n - 1}}{{,2}^{n - 1}}}}$, the halved $(n + 1)$-cube, the folded $(n + 1)$-cube, the graphs of alternating forms, the Taylor graph, the Hadamard graph, and incidence graphs of square designs.

Détail

Keywords: orbital graph, the Jevons group, distance-transitive graphs, Hamming graph, Taylor graph, Hadamard graph.

Bibliographie

[1] Povarov G.N., “O gruppovoi invariantnosti bulevykh funktsii.”, V sb. Primenenie logiki v nauke i tekhnike, AN SSSR, M., 1961, 263–340

[2] Bannai E., Ito. T., Algebraic Combinatorics, The Bejamin/Commings Publ. Comp., 1984 | MR | Zbl

[3] Pogorelov B.A., “Podmetriki metriki Khemminga i teorema A.A. Markova”, Trudy po diskretnoi matematike, 9 (2006), 190–219

[4] Pogorelov B.A., Pudovkina M.A., “Podmetriki metriki Khemminga i preobrazovaniya, rasprostranyayuschie iskazheniya v zadannoe chislo raz”, Trudy po diskretnoi matematike, 10 (2007), 202–238

[5] Pogorelov B.A., Pudovkina M.A., “Podmetriki Khemminga i ikh gruppy izometrii”, Trudy po diskretnoi matematike, 11:2 (2008), 32–68

[6] Pogorelov B.A., Pudovkina M.A., “Svoistva grafov orbitalov nadgrupp gruppy Dzhevonsa”, Matematicheskie voprosy kriptografii, 1:1 (2010), 55–84 | DOI

[7] Brouwer A.E., Cohen A.M., Neumaier A., Distance-Regular Graphs, Springer-Verlag, 1989 | MR | Zbl

[8] van Bon J., “Finite primitive distance-transitive graphs”, Eur. J. Comb., 28 (2007), 517–532 | DOI | MR | Zbl

[9] Ivanov A.A., “Distance-transitive graphs and their classification”, Investigations in algebraic theory of combinatorial objects, 1994, 283–378 | DOI | MR | Zbl

[10] Liebeck M.W., Saxl J., “The finite primitive permutation groups of rank three”, Bull. London Math. Soc., 18 (1986), 165–172 | DOI | MR | Zbl

[11] Praeger C.E., Saxl J., Yokoyama K., “Distance transitive graphs and finite simple groups”, Proc. London Math. Soc, 55 (1987), 1–21 | DOI | MR | Zbl

[12] Cohen A.M., “Distance-transitive graphs”, Encyclopedia of mathematics and its applications, 102, Cambridge University Press, 2004, 222–249 | Zbl

[13] Smith D.H., “Primitive and imprimitive graphs”, Quart. J. Math. Oxford, 22:2 (1971), 551–557 | DOI | MR | Zbl