×

Groups that are transitive on all partitions of a given shape. (English) Zbl 1319.05016

Summary: 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\leq i\leq 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\leq 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\leq i\leq r\). As an application, we determine which Johnson graphs are Cayley graphs.

MSC:

05A17 Combinatorial aspects of partitions of integers
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20B30 Symmetric groups
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beaumont, R.A., Peterson, R.P.: Set-transitive permutation groups. Canad. J. Math. 7, 35-42 (1955) · Zbl 0064.02504 · doi:10.4153/CJM-1955-005-x
[2] Bollobás, B.: Modern Graph theory. Graduate Texts in Mathematics, vol. 184. Springer, New York (1998) · Zbl 0902.05016
[3] Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol. 18. Springer, Berlin (1989) · Zbl 0747.05073
[4] Burnside, W.: Theory of Groups of Finite Order. Cambridge University Press, Cambridge (1897) · JFM 28.0118.03
[5] Butler, G., McKay, J.: The transitive groups of degree up to eleven. Commun. Algebra 11, 863-911 (1983) · Zbl 0518.20003 · doi:10.1080/00927878308822884
[6] Cameron, P.J.: Finite permutation groups and finite simple groups. Bull. Lond. Math. Soc. 13, 1-22 (1981) · Zbl 0463.20003 · doi:10.1112/blms/13.1.1
[7] Dixon, J.D., Mortimer, B.: Permutation Groups. Graduate Texts in Mathematics, vol. 163. Springer, New York (1996) · Zbl 0951.20001
[8] Godsil, C.D.: More odd graph theory. Discrete Math. 32, 205-207 (1980) · Zbl 0438.05053 · doi:10.1016/0012-365X(80)90055-2
[9] Godsil, C.D., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics, vol. 207. Springer, New York (2001) · Zbl 0968.05002
[10] Kantor, W.M.: \[k\] k-homogeneous groups. Math. Z. 124, 261-265 (1972) · Zbl 0232.20003 · doi:10.1007/BF01113919
[11] Livingstone, D., Wagner, A.: Transitivity of finite permutation groups on unordered sets. Math. Z. 90, 393-403 (1965) · Zbl 0136.28101 · doi:10.1007/BF01112361
[12] Martin, W.J., Sagan, B.E.: A new notion of transitivity for groups and sets of permutations. J. Lond. Math. Soc. 73, 1-13 (2006) · Zbl 1089.05079 · doi:10.1112/S0024610705022441
[13] Sabidussi, G.: On a class of fixed-point-free graphs. Proc. Am. Math. Soc. 9, 800-804 (1958) · Zbl 0091.37701 · doi:10.1090/S0002-9939-1958-0097068-7
[14] Wielandt, H.: Finite permutation groups, translated from the German by R. Bercov. Academic Press, New York (1964) · Zbl 0138.02501
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.