Available in electronic format
Available in print format
Transacrions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)
     

On partitioning the orbitals of a transitive permutation group

Author(s): Cai Heng Li; Cheryl E. Praeger
Journal: Trans. Amer. Math. Soc. 355 (2003), 637-653.
MSC (2000): Primary 20B15, 20B30, 05C25
Posted: September 19, 2002
Retrieve article in: PDF DVI PostScript

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:

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
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: 10.1090/S0002-9947-02-03110-0
PII: S 0002-9947(02)03110-0
Received by editor(s): October 23, 2001
Posted: September 19, 2002
Additional Notes: This work forms a part of an Australian Research Council grant project
Copyright of article: Copyright 2002, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google