Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



On Pyber's base size conjecture

Authors: Timothy C. Burness and Ákos Seress
Journal: Trans. Amer. Math. Soc. 367 (2015), 5633-5651
MSC (2010): Primary 20B15
Published electronically: February 3, 2015
MathSciNet review: 3347185
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 \vert G\vert/\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 [Enhancements On Off] (What's this?)

  • [1] C. Benbenishty, On actions of primitive groups, Ph.D. thesis, Hebrew University, Jerusalem, 2005.
  • [2] 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 (2008e:20003),
  • [3] 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 (2008m:20002),
  • [4] 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 (2012d:20003),
  • [5] 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 (2009m:20001),
  • [6] 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 (2011j:20035),
  • [7] Silvio Dolfi, Orbits of permutation groups on the power set, Arch. Math. (Basel) 75 (2000), no. 5, 321-327. MR 1785438 (2001g:20002),
  • [8] Joanna B. Fawcett, The base size of a primitive diagonal group, J. Algebra 375 (2013), 302-321. MR 2998958,
  • [9] 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 (2000a:20006),
  • [10] 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 (99b:20004),
  • [11] 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,
  • [12] Z. Halasi and K. Podoski, Every coprime linear group admits a base of size two, Trans. Amer. Math. Soc., to appear (arXiv:1212.0199v2)
  • [13] J. P. James, Partition actions of symmetric groups and regular bipartite graphs, Bull. London Math. Soc. 38 (2006), no. 2, 224-232. MR 2214474 (2007a:20004),
  • [14] 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 (90a:20008),
  • [15] 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 (89a:20002)
  • [16] Martin W. Liebeck and Aner Shalev, Simple groups, permutation groups, and probability, J. Amer. Math. Soc. 12 (1999), no. 2, 497-520. MR 1639620 (99h:20004),
  • [17] Martin W. Liebeck and Aner Shalev, Bases of primitive linear groups, J. Algebra 252 (2002), no. 1, 95-113. MR 1922387 (2003f:20005),
  • [18] Cheryl E. Praeger, The inclusion problem for finite primitive permutation groups, Proc. London Math. Soc. (3) 60 (1990), no. 1, 68-88. MR 1023805 (90j:20009),
  • [19] 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 (94g:20003)
  • [20] 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 (82e:20052)
  • [21] Ákos Seress, The minimal base size of primitive solvable permutation groups, J. London Math. Soc. (2) 53 (1996), no. 2, 243-255. MR 1373058 (96k:20003),
  • [22] Á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 (98g:20008),
  • [23] Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. MR 1970241 (2004c:20008)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 20B15

Retrieve articles in all journals with MSC (2010): 20B15

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

Ákos Seress
Affiliation: Department of Mathematics, The Ohio State University, 231 W 18th Avenue, Columbus, Ohio 43210

Keywords: Finite permutation groups, primitive groups, base size, Pyber's conjecture
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
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society