Automorphisms and regular embeddings of merged Johnson graphs (Q1767629): Difference between revisions

The vertices of the Johnson graph \(J(n,m)\) are the \(m\)-element subsets of an \(n\)-element set adjacent if their intersection has \(m-1\) elements. The distance \(i\) Johnson graph \(J(n,m)_i\) has the same set of vertices as \(J(n,m)\) with two vertices adjacent if they are of distance \(i\) in \(J(n,m)\). The merged Johnson graph \(J(n,m)_I\) is the edge-union of the graphs \(J(n,m)_i\), \( i \in I\), \( I \subseteq \{ 1,2, \dots, m \}\). The paper contains a full classification of the automorphism groups of generalized Johnson graphs. All of these graphs with the exception of \(J(12,4)\) with \(I= \{ 1,3 \}\) or \(I= \{ 2,4 \}\), \(J(n,(n-1)/2)\), and \(J(n,n/2)\), are shown to have their (full) automorphism group equal to \(S_n\) in its induced action on the \(m\)-element subsets of an \(n\)-element set. The proof is based on the classification of supergroups of \(S_n\) in its induced action completed by \textit{V. A. Ustimenko-Bakumovskij} [Sov. Math., Dokl. 18, 1433--1437 (1978; Zbl 0396.20002); translation from Dokl. Akad. Nauk SSSR 237, 276--279 (1977)]. Using this classification, the author succeeds at classifying all regular embeddings of merged Johnson graphs. Namely, it is shown that the only regular embeddings of merged Johnson graphs are the octahedral orientable embedding of \(J(4,2)_1\) and its non-orientable Petrie dual, two non-orientable embeddings of \(J(4,2)_{1,2} = K_6\), a Petrie dual pair of non-orientable embeddings of \(J(5,2)_1\), and a non-orientable embedding of Petersen \(J(5,2)_2\). It is also shown that none of the graphs \(J(n,m)_I\) where \( 5 \leq m < (n-1)/2 \) and \( \emptyset \subset I \subset \{ 1,2, \dots , m \} \) has a vertex-transitive embedding in an orientable or non-orientable surface.