On partitioning the orbitals of a transitive permutation group
HTML articles powered by AMS MathViewer
- by Cai Heng Li and Cheryl E. Praeger PDF
- Trans. Amer. Math. Soc. 355 (2003), 637-653 Request permission
Abstract:
Let $G$ be a permutation group on a set $\Omega$ with a transitive normal subgroup $M$. Then $G$ acts on the set $\mathrm {Orbl}(M,\Omega )$ of nontrivial $M$-orbitals in the natural way, and here we are interested in the case where $\mathrm {Orbl}(M,\Omega )$ has a partition $\mathcal P$ such that $G$ acts transitively on $\mathcal P$. The problem of characterising such tuples $(M,G,\Omega ,\mathcal P)$, called TODs, arises naturally in permutation group theory, and also occurs in number theory and combinatorics. The case where $|\mathcal P|$ is a prime-power is important in algebraic number theory in the study of arithmetically exceptional rational polynomials. The case where $|\mathcal P|=2$ exactly corresponds to self-complementary vertex-transitive graphs, while the general case corresponds to a type of isomorphic factorisation of complete graphs, called a homogeneous factorisation. Characterising homogeneous factorisations is an important problem in graph theory with applications to Ramsey theory. This paper develops a framework for the study of TODs, establishes some numerical relations between the parameters involved in TODs, gives some reduction results with respect to the $G$-actions on $\Omega$ and on $\mathcal P$, and gives some construction methods for TODs.References
- Brian Alspach, Joy Morris, and V. Vilfred, Self-complementary circulant graphs, Ars Combin. 53 (1999), 187–191. MR 1724502
- Peter J. Cameron, Finite permutation groups and finite simple groups, Bull. London Math. Soc. 13 (1981), no. 1, 1–22. MR 599634, DOI 10.1112/blms/13.1.1
- Neil J. Calkin, Paul Erdős, and Craig A. Tovey, New Ramsey bounds from cyclic graphs of prime order, SIAM J. Discrete Math. 10 (1997), no. 3, 381–387. MR 1459945, DOI 10.1137/S0895480196298378
- V. Chvátal, P. Erdős, and Z. Hedrlín, Ramsey’s theorem and self-complementary graphs, Discrete Math. 3 (1972), 301–304. MR 313119, DOI 10.1016/0012-365X(72)90087-8
- C. R. J. Clapham, A class of self-complementary graphs and lower bounds of some Ramsey numbers, J. Graph Theory 3 (1979), no. 3, 287–289. MR 542550, DOI 10.1002/jgt.3190030311
- Burton Fein, William M. Kantor, and Murray Schacher, Relative Brauer groups. II, J. Reine Angew. Math. 328 (1981), 39–57. MR 636194, DOI 10.1515/crll.1981.328.39
- Michael D. Fried, Robert Guralnick, and Jan Saxl, Schur covers and Carlitz’s conjecture, Israel J. Math. 82 (1993), no. 1-3, 157–225. MR 1239049, DOI 10.1007/BF02808112
- Dalibor Fronček, Alexander Rosa, and Jozef Širáň, The existence of selfcomplementary circulant graphs, European J. Combin. 17 (1996), no. 7, 625–628. MR 1407369, DOI 10.1006/eujc.1996.0053
- Daniel Gorenstein, Finite simple groups, University Series in Mathematics, Plenum Publishing Corp., New York, 1982. An introduction to their classification. MR 698782, DOI 10.1007/978-1-4684-8497-7
- R. M. Guralnick, C. H. Li, C. E. Praeger and J. Saxl, On orbital partitions and exceptionality of primitive permutation groups, preprint.
- R. M. Guralnick, P. Müller and J. Saxl, The rational function analogue of a question of Schur and exceptionality of permutation representations, Mem. Amer. Math. Soc. (to appear)
- Frank Harary, Robert W. Robinson, and Nicholas C. Wormald, Isomorphic factorisations. I. Complete graphs, Trans. Amer. Math. Soc. 242 (1978), 243–260. MR 545305, DOI 10.1090/S0002-9947-1978-0545305-1
- Frank Harary and Robert W. Robinson, Isomorphic factorizations. X. Unsolved problems, J. Graph Theory 9 (1985), no. 1, 67–86. MR 785650, DOI 10.1002/jgt.3190090105
- Robert Jajcay and Cai Heng Li, Constructions of self-complementary circulants with no multiplicative isomorphisms, European J. Combin. 22 (2001), no. 8, 1093–1100. MR 1861052, DOI 10.1006/eujc.2001.0529
- Cai Heng Li, On self-complementary vertex-transitive graphs, Comm. Algebra 25 (1997), no. 12, 3903–3908. MR 1481574, DOI 10.1080/00927879708826094
- C. H. Li, T. K. Lim and C. E. Praeger, Homogeneous factorisations of complete graphs with edge-transitive factors, in preparation.
- Cai Heng Li and Cheryl E. Praeger, Self-complementary vertex-transitive graphs need not be Cayley graphs, Bull. London Math. Soc. 33 (2001), no. 6, 653–661. MR 1853775, DOI 10.1112/S0024609301008505
- Valery Liskovets and Reinhard Pöschel, Non-Cayley-isomorphic self-complementary circulant graphs, J. Graph Theory 34 (2000), no. 2, 128–141. MR 1760418, DOI 10.1002/1097-0118(200006)34:2<128::AID-JGT2>3.0.CO;2-I
- Rudolf Mathon, On self-complementary strongly regular graphs, Discrete Math. 69 (1988), no. 3, 263–281. MR 940082, DOI 10.1016/0012-365X(88)90055-6
- Till Nierhoff, A tight bound on the irregularity strength of graphs, SIAM J. Discrete Math. 13 (2000), no. 3, 313–323. MR 1787985, DOI 10.1137/S0895480196314291
- Wojciech Peisert, All self-complementary symmetric graphs, J. Algebra 240 (2001), no. 1, 209–229. MR 1830551, DOI 10.1006/jabr.2000.8714
- Cheryl E. Praeger, Finite quasiprimitive graphs, Surveys in combinatorics, 1997 (London), London Math. Soc. Lecture Note Ser., vol. 241, Cambridge Univ. Press, Cambridge, 1997, pp. 65–85. MR 1477745, DOI 10.1017/CBO9780511662119.005
- S. B. Rao, On regular and strongly-regular self-complementary graphs, Discrete Math. 54 (1985), no. 1, 73–82. MR 787494, DOI 10.1016/0012-365X(85)90063-9
- Horst Sachs, Über selbstkomplementäre Graphen, Publ. Math. Debrecen 9 (1962), 270–288 (German). MR 151953
- D. A. Suprunenko, Self-complementary graphs, Kibernetika (Kiev) 5 (1985), i, 1–6, 24, 133 (Russian, with English summary). MR 821139
- Michio Suzuki, Gun ron. Vol. 1, Gendai Sūgaku [Modern Mathematics], vol. 18, Iwanami Shoten, Tokyo, 1977 (Japanese). MR 514842
- Bohdan Zelinka, Self-complementary vertex-transitive undirected graphs, Math. Slovaca 29 (1979), no. 1, 91–95 (English, with Russian summary). MR 561783
- Hong Zhang, Self-complementary symmetric graphs, J. Graph Theory 16 (1992), no. 1, 1–5. MR 1147798, DOI 10.1002/jgt.3190160102
Additional Information
- Cai Heng Li
- Affiliation: Department of Mathematics and Statistics, The University of Western Australia, Crawley, WA 6009, Australia
- MR Author ID: 305568
- Email: li@maths.uwa.edu.au
- Cheryl E. Praeger
- Affiliation: Department of Mathematics and Statistics, The University of Western Australia, Crawley, WA 6009, Australia
- MR Author ID: 141715
- ORCID: 0000-0002-0881-7336
- Email: praeger@maths.uwa.edu.au
- Received by editor(s): October 23, 2001
- Published electronically: September 19, 2002
- Additional Notes: This work forms a part of an Australian Research Council grant project
- © Copyright 2002 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 355 (2003), 637-653
- MSC (2000): Primary 20B15, 20B30, 05C25
- DOI: https://doi.org/10.1090/S0002-9947-02-03110-0
- MathSciNet review: 1932718