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 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 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.**Brian Alspach, Joy Morris, and V. Vilfred,*Self-complementary circulant graphs*, Ars Combin.**53**(1999), 187–191. MR**1724502****2.**Peter J. Cameron,*Finite permutation groups and finite simple groups*, Bull. London Math. Soc.**13**(1981), no. 1, 1–22. MR**599634**, 10.1112/blms/13.1.1**3.**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**, 10.1137/S0895480196298378**4.**V. Chvátal, P. Erdős, and Z. Hedrlín,*Ramsey’s theorem and self-complementary graphs*, Discrete Math.**3**(1972), 301–304. MR**0313119****5.**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**, 10.1002/jgt.3190030311**6.**Burton Fein, William M. Kantor, and Murray Schacher,*Relative Brauer groups. II*, J. Reine Angew. Math.**328**(1981), 39–57. MR**636194****7.**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**, 10.1007/BF02808112**8.**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**, 10.1006/eujc.1996.0053**9.**Daniel Gorenstein,*Finite simple groups*, University Series in Mathematics, Plenum Publishing Corp., New York, 1982. An introduction to their classification. MR**698782****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.**Frank Harary, Robert W. Robinson, and Nicholas C. Wormald,*Isomorphic factorisations. I. Complete graphs*, Trans. Amer. Math. Soc.**242**(1978), 243–260. MR**0545305**, 10.1090/S0002-9947-1978-0545305-1**13.**Frank Harary and Robert W. Robinson,*Isomorphic factorizations. X. Unsolved problems*, J. Graph Theory**9**(1985), no. 1, 67–86. MR**785650**, 10.1002/jgt.3190090105**14.**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**, 10.1006/eujc.2001.0529**15.**Cai Heng Li,*On self-complementary vertex-transitive graphs*, Comm. Algebra**25**(1997), no. 12, 3903–3908. MR**1481574**, 10.1080/00927879708826094**16.**C. H. Li, T. K. Lim and C. E. Praeger, Homogeneous factorisations of complete graphs with edge-transitive factors, in preparation.**17.**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**, 10.1112/S0024609301008505**18.**Valery Liskovets and Reinhard Pöschel,*Non-Cayley-isomorphic self-complementary circulant graphs*, J. Graph Theory**34**(2000), no. 2, 128–141. MR**1760418**, 10.1002/1097-0118(200006)34:2<128::AID-JGT2>3.0.CO;2-I**19.**Rudolf Mathon,*On self-complementary strongly regular graphs*, Discrete Math.**69**(1988), no. 3, 263–281. MR**940082**, 10.1016/0012-365X(88)90055-6**20.**Till Nierhoff,*A tight bound on the irregularity strength of graphs*, SIAM J. Discrete Math.**13**(2000), no. 3, 313–323 (electronic). MR**1787985**, 10.1137/S0895480196314291**21.**Wojciech Peisert,*All self-complementary symmetric graphs*, J. Algebra**240**(2001), no. 1, 209–229. MR**1830551**, 10.1006/jabr.2000.8714**22.**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**, 10.1017/CBO9780511662119.005**23.**S. B. Rao,*On regular and strongly-regular self-complementary graphs*, Discrete Math.**54**(1985), no. 1, 73–82. MR**787494**, 10.1016/0012-365X(85)90063-9**24.**Horst Sachs,*Über selbstkomplementäre Graphen*, Publ. Math. Debrecen**9**(1962), 270–288 (German). MR**0151953****25.**D. A. Suprunenko,*Self-complementary graphs*, Kibernetika (Kiev)**5**(1985), i, 1–6, 24, 133 (Russian, with English summary). MR**821139****26.**Michio Suzuki,*Group theory. I*, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 247, Springer-Verlag, Berlin-New York, 1982. Translated from the Japanese by the author. MR**648772****27.**Bohdan Zelinka,*Self-complementary vertex-transitive undirected graphs*, Math. Slovaca**29**(1979), no. 1, 91–95 (English, with Russian summary). MR**561783****28.**Hong Zhang,*Self-complementary symmetric graphs*, J. Graph Theory**16**(1992), no. 1, 1–5. MR**1147798**, 10.1002/jgt.3190160102

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