On problems concerning fixed-point-free permutations and on the polycirculant conjecture-a survey

Document Type: Research Paper

Authors

1 University of Larestan

2 University of Isfahan

3 Dipartimento di Matematica e Applicazioni, University of Milano-Bicocca,

Abstract

Fixed-point-free permutations‎, ‎also known as derangements‎, ‎have been studied for centuries‎. ‎In particular‎, ‎depending on their applications‎, ‎derangements of prime-power order and of prime order have always played a crucial role in a variety of different branches of mathematics‎: ‎from number theory to algebraic graph theory‎. ‎Substantial progress has been made on the study of derangements‎, ‎many long-standing open problems have been solved‎, ‎and many new research problems have arisen‎. ‎The results obtained and the methods developed in this area have also effectively been used to solve other problems regarding finite vertex-transitive graphs‎. ‎The methods used in this area range from deep group theory‎, ‎including the classification of the finite simple groups‎, ‎to combinatorial techniques‎. ‎This article is devoted to surveying results‎, ‎open problems and methods in this area‎.

Keywords

Main Subjects


[1] B. Alspach, Lifting Hamilton cycles of quotient graphs, Discrete Math. , 78 (1989) 25{36.
[2] A. Barb our, L. Holst and S. Janson, Poisson approximation . Oxford Science Publications. Clarendon Press, Oxford University Press, New York, 1992.
[3] E. Baticle, Le probleme des rencontres, Comptes Rendus Acad. Sci. Paris , 209 (1936) 724{726 and 1891{1892.
[4] N. Boston, W. Dabrowski, T. Foguel, P. J. Gies, J. Leawitt, D. T. Ose and D. A. Jackson, The prop ortion of xed-
p oint-free elements of a transitive p ermutation group, Comm. Algebra , 21 (1993) 3259{3275.
[5] D. Bubb oloni, S. Dol and P. Spiga, Finite groups whose irreducible characters vanish only on p -elements, J. Pure Appl. Algebra , 213 (2009) 370{376.
[6] T. C. Burness and M. Giudici, Lo cally elusive classical groups, Israel J. Math. , 225 (2018) 343{402.
[7] T. C. Burness and M. Giudici, Classical Groups, Derangements and Primes , Australian Mathematical So ciety lecture series 25, Cambridge University Press, 2016.
[8] T. C. Burness, M. Giudici and R.A. Wilson, Prime order derangements in primitive p ermutation groups, J. Algebra , 341 (2011) 158{178.
[9] T. C. Burness and H. P. Tong-Viet, Primitive p ermutation groups and derangements of prime p ower order, Manuscripta Math. , 150 (2015) 225{291.
[10] P. J. Cameron, Permutation Groups, London Mathematical Society Student Text , 45 , Cambridge University Press, Cambridge, 1999.
[11] P. J. Cameron, Some open problems on permutation groups , in: Groups, Combinatorics and Geometry, Durham, 1990, in: London Math. So c. Lecture Note Ser., 165 , Cambridge Univ. Press, Cambridge, 1992 340{350.
[12] P. J. Cameron (ed.), Problems from the Seventeenth British Combinatorial Conference, Discrete Math. , 231 (2001) 469{478.
[13] P. J. Cameron and M. A. Cohen, On the numb er of xed p oint free elements in a p ermutation group, A collection of contributions in honour of Jack van Lint, Discrete Math. , 106/107 (1992) 135{138.
[14] P. J. Cameron, P. Frankl and W. M. Kantor, Intersecting families of nite sets and xed-p oint-free 2-elements,
European J. Combin. , 10 (1989) 149{160.
[15] P. J. Cameron, M. Giudici, G. A. Jones, W. M. Kantor, M. H. Klin, D. Marusic and L. A. Nowitz, Transitive
p ermutation groups without semiregular subgroups, J. London Math. Soc. , 66 (2002) 325{333.
[16] P. J. Cameron, J. Sheehan and P. Spiga, Semiregular automorphisms of vertex-transitive cubic graphs, European J. Combin. , 27 (2006) 924{930.
[17] S. Chatterjee, P. Diaconis and E. Meckes, Exchangeable pairs and Poisson approximation, Probab. Surv. , 2 (2005) 64{106.

[18] E. Crestani and P .Spiga, Fixed-p oint-free elements in p -groups, Israel J. Math. , 180 (2010) 413{424.
[19] P. Diaconis, Group representations in probability and statistics , Lecture Notes Monograph Series 11, Institute of
Mathematical Statistics, Hayward, CA 1988.
[20] P. Diaconis, J. Fulman and R. Guralnick, On xed p oints of p ermutations, J. Algebraic Combin. , 28 (2007) 189{218.
[21] J. D. Dixon, B. Mortimer, Permutation groups , Springer-Verlag, New York, 1996.

[22] E. Dobson, Isomorphism problem for Cayley graphs of Z 3 p , Discrete Math. , 147 (1995) 87{94.
[23] E. Dobson, A. Malnic, D. Marusic and L. A. Nowitz, Minimal normal subgroups of transitive p ermutation groups of square-free degree, Discrete Math. , 307 (2007) 373{385.
[24] E. Dobson and D. Marusic, On semiregular elements of solvable groups, Comm. Algebra , 39 (2011) 1413{1426.
[25] L. Euler, Calcul de la probabilite dans le jeu de rencontre, Mem. Acad. Sci. Berlin , 7 (1753) 255{270.
[26] B. Fein, W. M. Kantor and M. Schacher, Relative Brauer groups I I, J. Reine Angew. Math. , 328 (1981) 39{57.
[27] M. Frechet, A note on the probl me des rencontres", American Mathematical Monthly , 46 (1939) 501.
[28] J. Fulman and R. Guralnick, Derangements in simple and primitive groups , in Groups, combinatorics, and geometry: Durham 2001, World Scienti c Publishing, 2003 99{121.
[29] J. Fulman, R. Guralnick, Bounds on the numb er and sizes of conjugacy classes in nite Chevalley groups with
applications to derangements, Amer. Math. Soc. , 364 (2012) 3023{3070.
[30] J. Fulman and R. Guralnick, Derangements in subspace actions of nite classical groups, Trans. Amer. Math. Soc., 364 (2017) 2521{2572.
[31] J. Fulman and R. Guralnick, Derangements in nite classical groups for actions related to extension eld and imprim- itive subgroups and the solution of the Boston-Shalev conjecture , preprint.
[32] M. Giudici, Quasiprimitive groups with no xed p oint free elements of prime order, J. London Math. Soc. (2) , 67
(2003) 73{84.
[33] M. Giudici, New constructions of groups without semiregular subgroups, Comm. Algebra , 35 (2007) 2719{2730.
[34] M. Giudici and J. Xu, All vertex-transitive lo cally-quasiprimitive graphs have a semiregular automorphism, J. Algebr. Comb. , 25 (2007) 217{232.
[35] M. Giudici and S. Kelly, Characterizing a family of elusive p ermutation groups, J. Group Theory , 12 (2009) 95{105.
[36] M. Giudici and G. Verret, Semiregular automorphisms in arc-transitive graphs of valency 2 p , in preparation.
[37] M. Giudici, P. Potocnik and G. Verret, Semiregular automorphisms of edge-transitive graphs, J. Algebr. Comb. , 40 (2014) 961{972.
[38] M. Giudici, L. Morgan, P. Poto cnik and G. Verret, Elusive groups of automorphisms of digraphs of small va-
lency, European J. Combin. , 64 (2015) 1{9.
[39] R. Guralnick, I. M. Isaacs and P. Spiga, On a relation b etween the rank and the prop ortion of derangements in nite transitive p ermutation groups, J. Combin. Theory Ser. A , 136 (2015) 198{200.
[40] R. Guralnick, M. Lieb eck, J. Saxl and A. Shalev, Random generation of nite simple groups, J. Algebra 219 (1999) 345{355.
[41] R. Guralnick and D. Wan, Bounds for xed p oint free elements in a transitive group and applications to curves over nite elds, Israel J. Math. , 101 (1997) 255{287.
[42] A. Hald, A History of Probability and Statistics and Their Applications Before 1750 , Wiley, New York, 1990.
[43] A. Hujdurovic, K. Kutnar and D. Marusic, Vertex-transitive generalized Cayley graphs which are not Cayley graphs, European J. Combin. , 46 (2015) 45{50.
[44] I. M. Isaacs, T. M. Keller and M. L. Lewis, A. Moreto, Transitive p ermutation groups in which all derangements are involutions, J. Pure Appl. Algebra , 207 (2006) 717{724.
[45] J. R. Isb ell, Homogeneous games, I I, Proc. Amer. Math . Soc. , 11 (1960) 159{161.
[46] G. Jones and M. Klin, On polycirculant graphs and groups , University of Southampton, Preprint N340, 2000.

[47] C. Jordan, Recherches sur les substitutions, J. Liouvil le , 17 (1872) 351{367
[48] D. Jordan, Eine Symmetrieeigenschaft von Graphen, in: Graphentheorie und ihre Anwendungen, Dresdner Reihe Forsch. , 9 (1988) 17{20.
[49] M. Klin, On transitive permutation groups without semi-regular subgroups , ICM 1998: International Congress of
Mathematicians, Berlin, 18-27 August 1998. Abstracts of short communications and p oster sessions, 1998.
[50] N. Klingen, Arithmetical Similarities{Prime Decomposition and Finite Group Theory , Oxford Sci. Publ., Oxford Univ. Press, Oxford,1998.
[51] K. Kutnar and D. Marusic, Recent trends and future directions in vertex-transitive graphs, Ars Math. Contemp. , 1 (2008) 112{125.
[52] K. Kutnar and P. Sparl, Distance-transitive graphs admit semiregular automorphisms, European J. Combin. , 31 (2010) 25{28.
[53] J. H. Lamb ert, Examen d'une espece de sup erstition ramenee au calcul des probabilites, Nouveau Mem. Acad. Roy. Sci. et Bel le-Lettres de Berlin , (1773) 411{420.
[54] P. S. de Laplace, Theorie Analytique des Probabilites , Paris, 1812.
[55] A. K. Lenstra, H. W. Lenstra, Jr., The development of the number eld sieve , Lecture Notes in Mathematics 1554, Springer-Verlag, Berlin, 1993.
[56] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse and J. M. Pollard, The factorization of the ninth Fermat numb er,
Math. Comp. , 61 (1993) 319{349.
[57] C. H. Li, Semiregular automorphisms of cubic vertex-transitive graphs, Proc. Amer. Math. Soc. , 136 (2008) 1905{1910.
[58] C. H. Li, C. E. Praeger, A. Venkatesh and S. Zhou, Finite lo cally-quasiprimitive graphs, Discrete Math. , 246 (2002) 197{218.
[59] D. Marusic, On vertex symmetric digraphs, Discrete Math. , 36 (1981) 69{81.
[60] D. Marusic, Semiregular automorphisms in vertex-transitive graphs with a solvable group of automorphisms, Ars Math. Contemp. , 13 (2017) 461{468.
[61] D. Marusic, Semiregular automorphisms in vertex-transitive graphs of order 3 p 2 , Electron. J. Combin. , 25 (2018).
[62] D. Marusic and T. D. Parsons, Hamiltonian paths in vertex-symmetric graphs of order 5 p , Discrete Math. , 42 (1982) 227{242.
[63] D. Marusic and T. D. Parsons, Hamiltonian paths in vertex-symmetric graphs of order 4 p , Discrete Math. , 43 (1983) 91{96.
[64] D. Marusic and R. Scap ellato, Permutation groups, vertex-transitive digraphs and semiregular automorphisms, Euro- pean . J. Combin. , 19 (1998) 707{712.
[65] D. Marusic, R. Scap ellato and N. Zagaglia Salvi, Generalized Cayley graphs, Discrete Math. , 102 (1992) 279{285.
[66] B. D. McKay and G .F. Royle, The transitive graphs with at most 26 vertices, Ars Combin. , 30 (1990) 161{176.
[67] K. Meagher, P. Spiga and P. H.Tiep, An Erd}os-Ko-Rado theorem for nite 2-transitive groups, European J. Combin. , 55 (2016) 100{118.
[68] K. Meagher and P. Spiga, An Erd}os-Ko-Rado theorem for the derangement graph of PGL 3 ( q ) acting on the pro jective plane, SIAM J. Discrete Math. , 28 (2014) 918{941.
[69] A. de Moivre, The Doctrine of Chances , Third Edition, Millar, London, 1756. Reprinted by Chelsea, New York, 1967.
[70] P. R. Montmort, Essay d'Analyse sur les Jeux de Hazard , Paris, Jacque Quillau, 1708.
[71] P. R. Montmort, Essay d'Analyse sur les Jeux de Hazard , Second edition, Paris, Jacque Quillau 1713.
[72] T. Pisanski and B. Servatius, Con gurations from a graphical viewpoint , Birkhauser Advanced Texts Basler Lehrb ucher Series, Birkhauser Boston Inc., Boston, 2013.
[73] R. Perlis, On the equation  K ( s ) =  K ( s ), J. Number Theory , 9 (1977) 342{360.
[74] J. S. Rose, A course on group theory , Cambridge University Press, Cambridge, 1978.

[75] G. R. Sanchis, Swapping Hats: A Generalization of Montmort's Problem, Mathematics Magazine , 71 (1998) 53{57.
[76] R. Scap ellato, Vertex-transitive graphs and digraphs , Graph symmetry: Algebraic metho ds and applications, Kluwer Academic Publisher, Netherlands, 1997 319{378.
[77] R. Scoville, The Hat-Check Problem, The American Mathematical Monthly , 73 (1966) 262{265.
[78] J-P. Serre, On a theorem of Jordan, Bul l. Amer. Math. Soc. , 40 (2003) 429{440.
[79] P. Spiga, Permutation characters and xed-p oint-free elements in p ermutation groups, J. Algebra , 299 (2006) 1{7.
[80] P. Spiga, Permutation 3-groups with no xed-p oint-free elements, Algebra Col loq. , 20 (2013) 383{394.
[81] P. Spiga, Semiregular elements in cubic vertex-transitive graphs and the restricted Burnside problem, Math. Proc. Cambridge Philos. Soc. , 157 (2014) 45{61.
[82] L. Takacs, The problem of coincidences, Arch. Hist. Exact Sci. , 21 (1979-1980) 229{244.
[83] G. Verret, Arc-transitive graphs of valency 8 have a semiregular automorphism, Ars Math. Contemp. , 8 (2015) 29{34.
[84] E. Waring, An Essay on the Principles of Human Know ledge , Cambridge, 1794.
[85] P. J. Weingb erger and L. P. Rothschild, Factoring p olynomials over algebraic numb er elds, ACM Trans. Math.
Software , 2 (1976) 335{350.
[86] H. W. Wielandt, Permutation groups through invariant relations and invariant functions , Lecture Notes, Ohio State University, 1969. Also publised in: Wielandt, Helmut, Mathematische Werke (Mathematical works), 1 Group theory, Walter de Gruyter & Co., Berlin, 1994 237{296.
[87] H. Wielandt, Finite permutation groups , Academic Press, New York, 1966.
[88] J. Xu, Semiregular automorphisms of arc-transitive graphs with valency pq , European J. Combin. , 29 (2008) 622{629.
[89] J. Xu, On elusive p ermutation groups of square-free degree, Comm. Algebra , 37 (2009) 3200{3206.