Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



On partitioning the orbitals of a transitive permutation group

Authors: Cai Heng Li and Cheryl E. Praeger
Journal: Trans. Amer. Math. Soc. 355 (2003), 637-653
MSC (2000): Primary 20B15, 20B30, 05C25
Published electronically: September 19, 2002
MathSciNet review: 1932718
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 $\vert\mathcal P\vert$ is a prime-power is important in algebraic number theory in the study of arithmetically exceptional rational polynomials. The case where $\vert\mathcal P\vert=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 [Enhancements On Off] (What's this?)

  • 1. B. Alspach, J. Morris and V. Vilfred, Self-complementary circulant graphs, Ars Combinatoria 53 (1999), 187-191. MR 2001b:05184
  • 2. P. Cameron, Finite permutation groups and finite simple groups, Bull. London Math. Soc 13 (1981), 1-22. MR 83m:20008
  • 3. N. J. Calkin, P. Erdös and C. A. Tovey, New Ramsey bounds from cyclic graphs of prime order, Siam J. Discrete Math. 10 (1997), 381-387. MR 98e:05078
  • 4. V. Chvátal, P. Erdös and Z. Hedrlín, Ramsey's theorem and self-complementary graphs, Disc. Math. 3(1972), 301-304. MR 47:1674
  • 5. C. R. J. Clapham, A class of self-complementary graphs and lower bounds of some Ramsey numbers, J. Graph Theory 3 (1979), 287-289. MR 81d:05054
  • 6. B. Fein, W. M. Kantor and M. Schacher, Relative Brauer groups II. J. Reine Angew. Math. 328 (1981), 39-57. MR 83a:12018
  • 7. M. Fried, R. Guralnick and J. Saxl, Schur covers and Carlitz's conjecture, Israel J. Math. 82 (1993), 157-225. MR 94j:12007
  • 8. D. Froncek, A. Rosa and J. Siran, The existence of self-complementary circulant graphs, European J. Combin. 17 (1996), 625-628. MR 97d:05235
  • 9. D. Gorenstein, Finite Simple Groups, 1982, Plenum Press, New York. MR 84j:20002
  • 10. R. M. Guralnick, C. H. Li, C. E. Praeger and J. Saxl, On orbital partitions and exceptionality of primitive permutation groups, preprint.
  • 11. 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)
  • 12. F. Harary, R. W. Robinson and N. C. Wormald, Isomorphic factorisations I: Complete graphs. Trans. Amer. Math. Soc. 242 (1978), 243-260. MR 58:27646a
  • 13. F. Harary and R. W. Robinson, Isomorphic factorisations X: unsolved problems, J. Graph Theory 9 (1985), 67-86. MR 87a:05111
  • 14. R. Jajcay and C. H. Li, Constructions of self-complementary circulants with no multiplicative isomorphisms, European J. Combin. 22 (2001), 1093-1100. MR 2002g:05098
  • 15. C. H. Li, On self-complementary vertex-transitive graphs, Comm. Algebra 25 (1997), 3903-3908. MR 98k:05119
  • 16. C. H. Li, T. K. Lim and C. E. Praeger, Homogeneous factorisations of complete graphs with edge-transitive factors, in preparation.
  • 17. C. H. Li and C. E. Praeger, Self-complementary vertex-transitive graphs need not be Cayley graphs, Bull. London Math. Soc. 33 (2001), 653-661. MR 2002h:05085
  • 18. V. Liskovets and R. Pöschel, Non-Cayley-isomorphic self-complementary circulant graphs, J. Graph Theory 34 (2000), 128-141. MR 2001e:05056
  • 19. R. Mathon, On selfcomplementary strongly regular graphs, Disc. Math. 69 (1988), 263-281. MR 89d:05150
  • 20. M. Muzychuk, On Sylow subgraphs of vertex-transitive self-complementary graphs, Bull. London Math. Soc. 31 (1999), 531-533. MR 2001i:05093
  • 21. W. Peisert, All self-complementary symmetric graphs, J. Algebra 240 (2001), 209-229. MR 2002e:05074
  • 22. C. E. Praeger, Finite quasiprimitive graphs, Surveys in Combinatorics 1997 (London), 65-85, London Math. Soc. Lecture Notes series 241, (Cambridge Univ. Press, Cambridge, 1997). MR 99b:05076
  • 23. S. B. Rao, On regular and strongly regular selfcomplementary graphs, Disc. Math. 54 (1985), 73-82. MR 86g:05089
  • 24. H. Sachs, Über selbstkomplementäre Graphen, Publ. Math. Debrecen 9 (1962), 270-288. MR 27:1934
  • 25. D. A. Suprunenko, Selfcomplementary graphs, Cybernetics 21 (1985), 559-567. MR 87g:05197
  • 26. M. Suzuki, Group Theory I, (Springer, New York 1982). MR 82k:20001c
  • 27. B. Zelinka, Self-complementary vertex-transitive undirected graphs, Math. Slovaca 29 (1979), 91-95. MR 81h:05116
  • 28. H. Zhang, Self-complementary symmetric graphs, J. Graph Theory 16 (1992), 1-5. MR 92k:05061

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 20B15, 20B30, 05C25

Retrieve articles in all journals with MSC (2000): 20B15, 20B30, 05C25

Additional Information

Cai Heng Li
Affiliation: Department of Mathematics and Statistics, The University of Western Australia, Crawley, WA 6009, Australia

Cheryl E. Praeger
Affiliation: Department of Mathematics and Statistics, The University of Western Australia, Crawley, WA 6009, Australia

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
Article copyright: © Copyright 2002 American Mathematical Society

American Mathematical Society