×

On Pyber’s base size conjecture. (English) Zbl 1316.20001

Summary: 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.

MSC:

20B15 Primitive groups
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] [Benbenishty] C. Benbenishty, On actions of primitive groups, Ph.D. thesis, Hebrew University, Jerusalem, 2005.
[2] Benbenishty, Carmit; Cohen, Jonathan A.; Niemeyer, Alice C., The minimum length of a base for the symmetric group acting on partitions, European J. Combin., 28, 6, 1575-1581 (2007) · Zbl 1120.05094 · doi:10.1016/j.ejc.2006.08.014
[3] Burness, Timothy C., On base sizes for actions of finite classical groups, J. Lond. Math. Soc. (2), 75, 3, 545-562 (2007) · Zbl 1128.20005 · doi:10.1112/jlms/jdm033
[4] Burness, Timothy C.; Guralnick, Robert M.; Saxl, Jan, On base sizes for symmetric groups, Bull. Lond. Math. Soc., 43, 2, 386-391 (2011) · Zbl 1222.20002 · doi:10.1112/blms/bdq123
[5] Burness, Timothy C.; Liebeck, Martin W.; Shalev, Aner, Base sizes for simple groups and a conjecture of Cameron, Proc. Lond. Math. Soc. (3), 98, 1, 116-162 (2009) · Zbl 1179.20002 · doi:10.1112/plms/pdn024
[6] Burness, Timothy C.; O’Brien, E. A.; Wilson, Robert A., Base sizes for sporadic simple groups, Israel J. Math., 177, 307-333 (2010) · Zbl 1216.20008 · doi:10.1007/s11856-010-0048-3
[7] Dolfi, Silvio, Orbits of permutation groups on the power set, Arch. Math. (Basel), 75, 5, 321-327 (2000) · Zbl 0978.20001 · doi:10.1007/s000130050510
[8] Fawcett, Joanna B., The base size of a primitive diagonal group, J. Algebra, 375, 302-321 (2013) · Zbl 1287.20004 · doi:10.1016/j.jalgebra.2012.11.020
[9] Gluck, David; Magaard, Kay, Base sizes and regular orbits for coprime affine permutation groups, J. London Math. Soc. (2), 58, 3, 603-618 (1998) · Zbl 0951.20003 · doi:10.1112/S0024610798006802
[10] Gluck, David; Seress, {\'A}kos; Shalev, Aner, Bases for primitive permutation groups and a conjecture of Babai, J. Algebra, 199, 2, 367-378 (1998) · Zbl 0897.20005 · doi:10.1006/jabr.1997.7149
[11] Halasi, Zolt{\'a}n, On the base size for the symmetric group acting on subsets, Studia Sci. Math. Hungar., 49, 4, 492-500 (2012) · Zbl 1296.20002 · doi:10.1556/SScMath.49.2012.4.1222
[12] [HP] Z. Halasi and K. Podoski, Every coprime linear group admits a base of size two, Trans. Amer. Math. Soc., to appear (arXiv:1212.0199v2) · Zbl 1382.20012
[13] James, J. P., Partition actions of symmetric groups and regular bipartite graphs, Bull. London Math. Soc., 38, 2, 224-232 (2006) · Zbl 1159.20003 · doi:10.1112/S0024609306018285
[14] Kov{\'a}cs, L. G., Primitive subgroups of wreath products in product action, Proc. London Math. Soc. (3), 58, 2, 306-322 (1989) · Zbl 0671.20002 · doi:10.1112/plms/s3-58.2.306
[15] Liebeck, Martin W.; Praeger, Cheryl E.; Saxl, Jan, On the O’Nan-Scott theorem for finite primitive permutation groups, J. Austral. Math. Soc. Ser. A, 44, 3, 389-396 (1988) · Zbl 0647.20005
[16] Liebeck, Martin W.; Shalev, Aner, Simple groups, permutation groups, and probability, J. Amer. Math. Soc., 12, 2, 497-520 (1999) · Zbl 0916.20003 · doi:10.1090/S0894-0347-99-00288-X
[17] Liebeck, Martin W.; Shalev, Aner, Bases of primitive linear groups, J. Algebra, 252, 1, 95-113 (2002) · Zbl 1034.20001 · doi:10.1016/S0021-8693(02)00001-7
[18] Praeger, Cheryl E., The inclusion problem for finite primitive permutation groups, Proc. London Math. Soc. (3), 60, 1, 68-88 (1990) · Zbl 0653.20005 · doi:10.1112/plms/s3-60.1.68
[19] Pyber, L{\'a}szl{\'o}, Asymptotic results for permutation groups. Groups and computation, New Brunswick, NJ, 1991, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 11, 197-219 (1993), Amer. Math. Soc.: Providence, RI:Amer. Math. Soc. · Zbl 0799.20005
[20] Scott, Leonard L., Representations in characteristic \(p\). The Santa Cruz Conference on Finite Groups (Univ. California, Santa Cruz, Calif., 1979), Proc. Sympos. Pure Math. 37, 319-331 (1980), Amer. Math. Soc.: Providence, R.I.:Amer. Math. Soc.
[21] Seress, {\'A}kos, The minimal base size of primitive solvable permutation groups, J. London Math. Soc. (2), 53, 2, 243-255 (1996) · Zbl 0854.20004 · doi:10.1112/jlms/53.2.243
[22] Seress, {\'A}kos, Primitive groups with no regular orbits on the set of subsets, Bull. London Math. Soc., 29, 6, 697-704 (1997) · Zbl 0892.20002 · doi:10.1112/S0024609397003536
[23] Seress, {\'A}kos, Permutation group algorithms, Cambridge Tracts in Mathematics 152, x+264 pp. (2003), Cambridge University Press: Cambridge:Cambridge University Press · Zbl 1028.20002 · doi:10.1017/CBO9780511546549
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.