On Pyber’s base size conjecture
HTML articles powered by AMS MathViewer
- by Timothy C. Burness and Ákos Seress PDF
- Trans. Amer. Math. Soc. 367 (2015), 5633-5651 Request permission
Abstract:
Let $G$ be a permutation group on a finite set $\Omega$. A subset of $\Omega$ is a base for $G$ if its pointwise stabilizer in $G$ is trivial. The base size of $G$, denoted $b(G)$, is the smallest size of a base. A well-known conjecture of Pyber from the early 1990s asserts that there exists an absolute constant $c$ such that $b(G) \leqslant c\log |G|/\log n$ for any primitive permutation group $G$ of degree $n$. Several special cases have been verified in recent years, including the almost simple and diagonal cases. In this paper, we prove Pyber’s conjecture for all non-affine primitive groups.References
- C. Benbenishty, On actions of primitive groups, Ph.D. thesis, Hebrew University, Jerusalem, 2005.
- Carmit Benbenishty, Jonathan A. Cohen, and Alice C. Niemeyer, The minimum length of a base for the symmetric group acting on partitions, European J. Combin. 28 (2007), no. 6, 1575–1581. MR 2339486, DOI 10.1016/j.ejc.2006.08.014
- Timothy C. Burness, On base sizes for actions of finite classical groups, J. Lond. Math. Soc. (2) 75 (2007), no. 3, 545–562. MR 2352720, DOI 10.1112/jlms/jdm033
- Timothy C. Burness, Robert M. Guralnick, and Jan Saxl, On base sizes for symmetric groups, Bull. Lond. Math. Soc. 43 (2011), no. 2, 386–391. MR 2781219, DOI 10.1112/blms/bdq123
- Timothy C. Burness, Martin W. Liebeck, and Aner Shalev, Base sizes for simple groups and a conjecture of Cameron, Proc. Lond. Math. Soc. (3) 98 (2009), no. 1, 116–162. MR 2472163, DOI 10.1112/plms/pdn024
- Timothy C. Burness, E. A. O’Brien, and Robert A. Wilson, Base sizes for sporadic simple groups, Israel J. Math. 177 (2010), 307–333. MR 2684423, DOI 10.1007/s11856-010-0048-3
- Silvio Dolfi, Orbits of permutation groups on the power set, Arch. Math. (Basel) 75 (2000), no. 5, 321–327. MR 1785438, DOI 10.1007/s000130050510
- Joanna B. Fawcett, The base size of a primitive diagonal group, J. Algebra 375 (2013), 302–321. MR 2998958, DOI 10.1016/j.jalgebra.2012.11.020
- David Gluck and Kay Magaard, Base sizes and regular orbits for coprime affine permutation groups, J. London Math. Soc. (2) 58 (1998), no. 3, 603–618. MR 1678153, DOI 10.1112/S0024610798006802
- David Gluck, Ákos Seress, and Aner Shalev, Bases for primitive permutation groups and a conjecture of Babai, J. Algebra 199 (1998), no. 2, 367–378. MR 1489917, DOI 10.1006/jabr.1997.7149
- Zoltán Halasi, On the base size for the symmetric group acting on subsets, Studia Sci. Math. Hungar. 49 (2012), no. 4, 492–500. MR 3098294, DOI 10.1556/SScMath.49.2012.4.1222
- Z. Halasi and K. Podoski, Every coprime linear group admits a base of size two, Trans. Amer. Math. Soc., to appear (arXiv:1212.0199v2)
- J. P. James, Partition actions of symmetric groups and regular bipartite graphs, Bull. London Math. Soc. 38 (2006), no. 2, 224–232. MR 2214474, DOI 10.1112/S0024609306018285
- L. G. Kovács, Primitive subgroups of wreath products in product action, Proc. London Math. Soc. (3) 58 (1989), no. 2, 306–322. MR 977479, DOI 10.1112/plms/s3-58.2.306
- Martin W. Liebeck, Cheryl E. Praeger, and Jan Saxl, On the O’Nan-Scott theorem for finite primitive permutation groups, J. Austral. Math. Soc. Ser. A 44 (1988), no. 3, 389–396. MR 929529
- Martin W. Liebeck and Aner Shalev, Simple groups, permutation groups, and probability, J. Amer. Math. Soc. 12 (1999), no. 2, 497–520. MR 1639620, DOI 10.1090/S0894-0347-99-00288-X
- Martin W. Liebeck and Aner Shalev, Bases of primitive linear groups, J. Algebra 252 (2002), no. 1, 95–113. MR 1922387, DOI 10.1016/S0021-8693(02)00001-7
- Cheryl E. Praeger, The inclusion problem for finite primitive permutation groups, Proc. London Math. Soc. (3) 60 (1990), no. 1, 68–88. MR 1023805, DOI 10.1112/plms/s3-60.1.68
- László Pyber, Asymptotic results for permutation groups, Groups and computation (New Brunswick, NJ, 1991) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11, Amer. Math. Soc., Providence, RI, 1993, pp. 197–219. MR 1235804
- Leonard L. Scott, Representations in characteristic $p$, The Santa Cruz Conference on Finite Groups (Univ. California, Santa Cruz, Calif., 1979) Proc. Sympos. Pure Math., vol. 37, Amer. Math. Soc., Providence, R.I., 1980, pp. 319–331. MR 604599
- Ákos Seress, The minimal base size of primitive solvable permutation groups, J. London Math. Soc. (2) 53 (1996), no. 2, 243–255. MR 1373058, DOI 10.1112/jlms/53.2.243
- Ákos Seress, Primitive groups with no regular orbits on the set of subsets, Bull. London Math. Soc. 29 (1997), no. 6, 697–704. MR 1468057, DOI 10.1112/S0024609397003536
- Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. MR 1970241, DOI 10.1017/CBO9780511546549
Additional Information
- Timothy C. Burness
- Affiliation: School of Mathematics, University of Southampton, Southampton SO17 1BJ, United Kingdom
- Address at time of publication: School of Mathematics, University of Bristol, Bristol BS8 1TW, United Kingdom
- MR Author ID: 717073
- Email: t.burness@soton.ac.uk, t.burness@bristol.ac.uk
- Ákos Seress
- Affiliation: Department of Mathematics, The Ohio State University, 231 W 18th Avenue, Columbus, Ohio 43210
- Email: akos@math.ohio-state.edu
- Received by editor(s): April 8, 2013
- Received by editor(s) in revised form: June 19, 2013
- Published electronically: February 3, 2015
- Additional Notes: The first author was supported by EPSRC grant EP/I019545/1, and he thanks the Department of Mathematics at The Ohio State University for its generous hospitality
Ákos Seress passed away on February 13, 2013, shortly before this paper was submitted for publication - © Copyright 2015 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 367 (2015), 5633-5651
- MSC (2010): Primary 20B15
- DOI: https://doi.org/10.1090/S0002-9947-2015-06224-2
- MathSciNet review: 3347185