Rank 3 Transitive Decompositions of Complete Multipartite Graphs

Rank 3 transitive decompositions of complete multipartite graphs-Pearce-Praeger.pdf

0 Abstract

A transitive decomposition of a graph is a partition of the edge or arc set giving a set of subgraphs which are preserved and permuted transitively by a group of automorphisms of the graph.

This paper deals with transitive decompositions of complete multipartite graphs preserved by an imprimitive rank 3 permutation group. We obtain a near-complete classification of these when the group in question has an almost simple component.

1 Introduction

Definition

A transitive decomposition of a graph $\Gamma$ is a pair $(\Gamma ,\mathcal{P})$, where $\mathcal{P}$ is a partition of the arc set $\mathrm{A\Gamma }$, such that there is a group $G$ of automorphisms of $\Gamma$ satisfying the following two conditions:

• $G$ leaves the partition $\mathcal{P}$ invariant; and
• $G$ acts transitively in its induced action on $\mathcal{P}$.

We call $(\Gamma ,\mathcal{P})$ a $G$-transitive decomposition.

In Transitive decompositions of graph products - rank 3 grid type, we gave a characterization of transitive decompositions preserved by a primitive rank $3$ group of grid type.

Let $|\mathcal{B}|=n$ and let $m$ be the size of the blocks in $\mathcal{B}$. Then $G$ acts as a group of automorphisms of the complete multipartite graph $K_{n\times m}$, whose vertex set is $\Omega$, and whose edges are the pairs of vertices that lie in different blocks in $\mathcal{B}$.

Main theorem

Theorem

In (iii) and (iv), $X$ is $2$-transitive because $G$ has rank $3$ by [[Finite permutation groups of rank $3$#^06f0s7|this]]. These $X$-transitive decompositions were characterized by On classifying finite edge colored graphs with two transitive automorphism groups-Sibley.

Key to the proof is a classification of imprimitive rank $3$ subgroups of $S_m\wr S_n$ on $mn$ points with almost simple component $H$, which is mentioned in On imprimitive rank 3 permutation groups.

Definitions for the theorem

Let $\Sigma$ be a graph with vertex set $\{1,\cdots ,n\}$, and let $N_m$ denote the null graph with $m$ vertices and no arcs. We use lowercase Greek letters for the vertices of $N_m$. Then $\Sigma [N_m]$ is the graph with vertex set $\mathrm{V}\Sigma \times \mathrm{V}{N}_m$ and arcs $((i,\alpha ),(j,\beta ))$ whenever $(i,j)\in \mathrm{A}\Sigma$. When $\Sigma =K_n$, the graph $K_n[N_m]$ is isomorphic to the complete multipartite graph $K_{n\times m}$.

Let $\Sigma$ be a graph, let $\mathcal{R}$ be a partition of $\mathrm{A}\Sigma$, and let $m>0$ be an integer. For each $R\in \mathcal{R}$, let $R[N_m]=\{((i,\alpha ),(j,\beta )):\alpha ,\beta \in \mathrm{V}{N}_n,(i,j)\in R={\bigcup }_{i,j\in R}(i,j)[N_m]\},$and let $\mathrm{Lex}(\mathcal{R},m)$ be the set of all such subsets $R[N_m]$ of the arc set of $\Sigma [N_m]$, for all $R\in \mathcal{R}$.

2 Construction for transitive decompositions