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

DOI:
https://doi.org/10.1090/S0002-9947-02-03110-0

Published electronically:
September 19, 2002

MathSciNet review:
1932718

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let be a permutation group on a set with a transitive normal subgroup . Then acts on the set of nontrivial -orbitals in the natural way, and here we are interested in the case where has a partition such that acts transitively on . The problem of characterising such tuples , called TODs, arises naturally in permutation group theory, and also occurs in number theory and combinatorics. The case where is a prime-power is important in algebraic number theory in the study of arithmetically exceptional rational polynomials. The case where 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 -actions on and on , and gives some construction methods for TODs.

**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**

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

Email:
li@maths.uwa.edu.au

**Cheryl E. Praeger**

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

Email:
praeger@maths.uwa.edu.au

DOI:
https://doi.org/10.1090/S0002-9947-02-03110-0

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