On partitioning the orbitals of a transitive permutation group
Authors:
Cai Heng Li and Cheryl E. Praeger
Journal:
Trans. Amer. Math. Soc. 355 (2003), 637653
MSC (2000):
Primary 20B15, 20B30, 05C25
Published electronically:
September 19, 2002
MathSciNet review:
1932718
Fulltext PDF Free Access
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 primepower is important in algebraic number theory in the study of arithmetically exceptional rational polynomials. The case where exactly corresponds to selfcomplementary vertextransitive 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, Selfcomplementary circulant graphs, Ars Combinatoria 53 (1999), 187191. MR 2001b:05184
 2.
P. Cameron, Finite permutation groups and finite simple groups, Bull. London Math. Soc 13 (1981), 122. 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), 381387. MR 98e:05078
 4.
V. Chvátal, P. Erdös and Z. Hedrlín, Ramsey's theorem and selfcomplementary graphs, Disc. Math. 3(1972), 301304. MR 47:1674
 5.
C. R. J. Clapham, A class of selfcomplementary graphs and lower bounds of some Ramsey numbers, J. Graph Theory 3 (1979), 287289. MR 81d:05054
 6.
B. Fein, W. M. Kantor and M. Schacher, Relative Brauer groups II. J. Reine Angew. Math. 328 (1981), 3957. MR 83a:12018
 7.
M. Fried, R. Guralnick and J. Saxl, Schur covers and Carlitz's conjecture, Israel J. Math. 82 (1993), 157225. MR 94j:12007
 8.
D. Froncek, A. Rosa and J. Siran, The existence of selfcomplementary circulant graphs, European J. Combin. 17 (1996), 625628. 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), 243260. MR 58:27646a
 13.
F. Harary and R. W. Robinson, Isomorphic factorisations X: unsolved problems, J. Graph Theory 9 (1985), 6786. MR 87a:05111
 14.
R. Jajcay and C. H. Li, Constructions of selfcomplementary circulants with no multiplicative isomorphisms, European J. Combin. 22 (2001), 10931100. MR 2002g:05098
 15.
C. H. Li, On selfcomplementary vertextransitive graphs, Comm. Algebra 25 (1997), 39033908. MR 98k:05119
 16.
C. H. Li, T. K. Lim and C. E. Praeger, Homogeneous factorisations of complete graphs with edgetransitive factors, in preparation.
 17.
C. H. Li and C. E. Praeger, Selfcomplementary vertextransitive graphs need not be Cayley graphs, Bull. London Math. Soc. 33 (2001), 653661. MR 2002h:05085
 18.
V. Liskovets and R. Pöschel, NonCayleyisomorphic selfcomplementary circulant graphs, J. Graph Theory 34 (2000), 128141. MR 2001e:05056
 19.
R. Mathon, On selfcomplementary strongly regular graphs, Disc. Math. 69 (1988), 263281. MR 89d:05150
 20.
M. Muzychuk, On Sylow subgraphs of vertextransitive selfcomplementary graphs, Bull. London Math. Soc. 31 (1999), 531533. MR 2001i:05093
 21.
W. Peisert, All selfcomplementary symmetric graphs, J. Algebra 240 (2001), 209229. MR 2002e:05074
 22.
C. E. Praeger, Finite quasiprimitive graphs, Surveys in Combinatorics 1997 (London), 6585, 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), 7382. MR 86g:05089
 24.
H. Sachs, Über selbstkomplementäre Graphen, Publ. Math. Debrecen 9 (1962), 270288. MR 27:1934
 25.
D. A. Suprunenko, Selfcomplementary graphs, Cybernetics 21 (1985), 559567. MR 87g:05197
 26.
M. Suzuki, Group Theory I, (Springer, New York 1982). MR 82k:20001c
 27.
B. Zelinka, Selfcomplementary vertextransitive undirected graphs, Math. Slovaca 29 (1979), 9195. MR 81h:05116
 28.
H. Zhang, Selfcomplementary symmetric graphs, J. Graph Theory 16 (1992), 15. MR 92k:05061
 1.
 B. Alspach, J. Morris and V. Vilfred, Selfcomplementary circulant graphs, Ars Combinatoria 53 (1999), 187191. MR 2001b:05184
 2.
 P. Cameron, Finite permutation groups and finite simple groups, Bull. London Math. Soc 13 (1981), 122. 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), 381387. MR 98e:05078
 4.
 V. Chvátal, P. Erdös and Z. Hedrlín, Ramsey's theorem and selfcomplementary graphs, Disc. Math. 3(1972), 301304. MR 47:1674
 5.
 C. R. J. Clapham, A class of selfcomplementary graphs and lower bounds of some Ramsey numbers, J. Graph Theory 3 (1979), 287289. MR 81d:05054
 6.
 B. Fein, W. M. Kantor and M. Schacher, Relative Brauer groups II. J. Reine Angew. Math. 328 (1981), 3957. MR 83a:12018
 7.
 M. Fried, R. Guralnick and J. Saxl, Schur covers and Carlitz's conjecture, Israel J. Math. 82 (1993), 157225. MR 94j:12007
 8.
 D. Froncek, A. Rosa and J. Siran, The existence of selfcomplementary circulant graphs, European J. Combin. 17 (1996), 625628. 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), 243260. MR 58:27646a
 13.
 F. Harary and R. W. Robinson, Isomorphic factorisations X: unsolved problems, J. Graph Theory 9 (1985), 6786. MR 87a:05111
 14.
 R. Jajcay and C. H. Li, Constructions of selfcomplementary circulants with no multiplicative isomorphisms, European J. Combin. 22 (2001), 10931100. MR 2002g:05098
 15.
 C. H. Li, On selfcomplementary vertextransitive graphs, Comm. Algebra 25 (1997), 39033908. MR 98k:05119
 16.
 C. H. Li, T. K. Lim and C. E. Praeger, Homogeneous factorisations of complete graphs with edgetransitive factors, in preparation.
 17.
 C. H. Li and C. E. Praeger, Selfcomplementary vertextransitive graphs need not be Cayley graphs, Bull. London Math. Soc. 33 (2001), 653661. MR 2002h:05085
 18.
 V. Liskovets and R. Pöschel, NonCayleyisomorphic selfcomplementary circulant graphs, J. Graph Theory 34 (2000), 128141. MR 2001e:05056
 19.
 R. Mathon, On selfcomplementary strongly regular graphs, Disc. Math. 69 (1988), 263281. MR 89d:05150
 20.
 M. Muzychuk, On Sylow subgraphs of vertextransitive selfcomplementary graphs, Bull. London Math. Soc. 31 (1999), 531533. MR 2001i:05093
 21.
 W. Peisert, All selfcomplementary symmetric graphs, J. Algebra 240 (2001), 209229. MR 2002e:05074
 22.
 C. E. Praeger, Finite quasiprimitive graphs, Surveys in Combinatorics 1997 (London), 6585, 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), 7382. MR 86g:05089
 24.
 H. Sachs, Über selbstkomplementäre Graphen, Publ. Math. Debrecen 9 (1962), 270288. MR 27:1934
 25.
 D. A. Suprunenko, Selfcomplementary graphs, Cybernetics 21 (1985), 559567. MR 87g:05197
 26.
 M. Suzuki, Group Theory I, (Springer, New York 1982). MR 82k:20001c
 27.
 B. Zelinka, Selfcomplementary vertextransitive undirected graphs, Math. Slovaca 29 (1979), 9195. MR 81h:05116
 28.
 H. Zhang, Selfcomplementary symmetric graphs, J. Graph Theory 16 (1992), 15. 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
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:
http://dx.doi.org/10.1090/S0002994702031100
PII:
S 00029947(02)031100
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
