Groups that are transitive on all partitions of a given shape

Dobson, Edward ; Malnič, Aleksander

Journal of Algebraic Combinatorics, Tome 42 (2015) no. 2, pp. 605-617.

Résumé

Let $[n] = K_1\dot{\cup }K_2 \dot{\cup }\cdots \dot{\cup }K_r$ be a partition of $[n] = \{1,2,\dots ,n\}$ and set $\ell _i = |K_i|$ for $1\le i\le r$. Then the tuple $P = \{K_1,K_2,\dots,K_r\}$ is an unordered partition of $[n]$ of shape $[\ell _1,\dots,\ell _r]$. Let ${{\mathcal {P}}}$ be the set of all partitions of $[n]$ of shape $[\ell _1,\dots,\ell _r]$. Given a fixed shape $[\ell _1,\dots ,\ell _r]$, we determine all subgroups $G\le S_n$ that are transitive on ${{\mathcal {P}}}$ in the following sense: Whenever $P = \{K_1,\dots ,K_r\}$ and $P^\prime= \{K_1^\prime,\dots,K_r^\prime\}$ are partitions of $[n]$ of shape $[\ell _1,\dots,\ell _r]$, there exists $g\in G$ such that $g(P) = P^\prime$, that is, $\{g(K_1),\dots,g(K_r)\} = \{K_1^\prime,\dots,K_r^\prime\}$. Moreover, for an ordered shape, we determine all subgroups of $S_n$ that are transitive on the set of all ordered partitions of the given shape. That is, with $P$ and $P^\prime$ as above, $g(K_i) = K_i^\prime$ for $1\le i\le r$. As an application, we determine which Johnson graphs are Cayley graphs.

Détail

Classification : 05A17, 05C25, 20B30
Keywords: transitive group, ordered partition, unordered partition, Johnson graph, Cayley graph