A proof of Pyber's base size conjecture

DOI10.1016/J.AIM.2018.04.009MaRDI QIDQ1647396zbMATH OpenOpenAlexWikidataFDO

Authors Hülya Duyan, Zoltán Halasi, Attila Maróti

Publication date 26 June 2018

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.09487, http://real.mtak.hu/86094/1/DuyanHalasiMaroti.pdf

zbMATH Keywords

permutation grouplinear groupdistinguishing numberminimal base size

Mathematics Subject Classification ID

Primitive groups (20B15) Representations of finite symmetric groups (20C30) Computational methods for problems pertaining to group theory (20-08)

Abstract: Building on earlier papers of several authors, we establish that there exists a universal constant $c>0$ such that the minimal base size $b(G)$ of a primitive permutation group $G$ of degree $n$ satisfies $log|G|/lognleqb(G)<45(log|G|/logn)+c$. This finishes the proof of Pyber's base size conjecture. An ingredient of the proof is that for the distinguishing number $d(G)$ (in the sense of Albertson and Collins) of a transitive permutation group $G$ of degree $n>1$ we have the estimates $sqrt[n]|G|<d(G)leq48sqrt[n]|G|$.

Recommendations

• On Pyber's base size conjecture.
• A Proof of a Conjecture of Knuth
• A proof of the Bender-Knuth conjecture
• On the base sequence conjecture
• A proof of the Erdős primitive set conjecture
• Proof of a conjecture of Erdős and Turán
• A proof of the Erdős-Faber-Lovász conjecture
• A proof of Sethares' conjecture
• A proof of the Erdös-Sands-Sauer-Woodrow conjecture
• A proof of Boesch's conjecture

Cites work

• scientific article; zbMATH DE number 3717558 (Why is no real title available?)
• scientific article; zbMATH DE number 46357 (Why is no real title available?)
• scientific article; zbMATH DE number 1261512 (Why is no real title available?)
• scientific article; zbMATH DE number 475365 (Why is no real title available?)
• scientific article; zbMATH DE number 1981753 (Why is no real title available?)
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• Arithmetic results on orbits of linear groups
• Base Sizes and Regular Orbits for Coprime Affine Permutation Groups
• Base size, metric dimension and other invariants of groups and graphs
• Base sizes for simple groups and a conjecture of Cameron
• Base sizes for sporadic simple groups.
• Base sizes of imprimitive linear groups and orbits of general linear groups on spanning tuples
• Base sizes of primitive groups: bounds with explicit constants
• Bases for primitive permutation groups and a conjecture of Babai
• Bases of primitive linear groups.
• Bases of primitive linear groups. II.
• Character degrees and random walks in finite groups of Lie type
• Every coprime linear group admits a base of size two
• Finite permutation groups with a transitive minimal normal subgroup
• Minimum bases for permutation groups: The greedy approximation
• Normalizers of primitive permutation groups
• On Pyber's base size conjecture.
• On base sizes for actions of finite classical groups
• On base sizes for symmetric groups
• On minimal degrees and base sizes of primitive permutation groups
• On the base size and rank of a primitive permutation group
• On the order of doubly transitive permutation groups
• On the order of uniprimitive permutation groups
• On the orders of doubly transitive permutation groups, elementary estimates
• On the orders of primitive groups with restricted nonabelian composition factors
• Orbits of permutation groups on the power set
• Primitive Groups with no Regular Orbits on the Set of Subsets
• Random Permutations: Some Group-Theoretic Aspects
• Random generation of finite and profinite groups and group enumeration.
• Simple groups, permutation groups, and probability
• Symmetry breaking in graphs
• The Minimal Base Size of Primitive Solvable Permutation Groups
• The base size of a primitive diagonal group.
• The minimal base size for a \(p\)-solvable linear group

Cited in

(25)

• Minimal degree, base size, order: selected topics on primitive permutation groups
• Bases of twisted wreath products
• On the single-orbit conjecture for uncoverings-by-bases
• Primitive permutation groups as products of point stabilizers
• On the regularity number of a finite group and other base-related invariants
• Base Sizes and Regular Orbits for Coprime Affine Permutation Groups
• Bases of primitive linear groups.
• Orbit closed permutation groups, relation groups, and simple groups
• On base sizes for primitive groups of product type
• Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's conjecture confirmed
• Permutation groups with restricted stabilizers
• On the Burness-Giudici conjecture
• Base sizes of primitive groups of diagonal type
• The maximal size of a minimal generating set
• On the Saxl graphs of primitive groups with soluble stabilisers
• Normalisers of primitive permutation groups in quasipolynomial time
• On Pyber's base size conjecture.
• Bases for quasisimple linear groups
• Bases of primitive linear groups. II.
• The distinguishing number of quasiprimitive and semiprimitive groups
• On the orders of doubly transitive permutation groups, elementary estimates
• Derangements in wreath products of permutation groups
• Base sizes for primitive groups with soluble stabilisers
• On base sizes for symmetric groups
• Base sizes of primitive groups: bounds with explicit constants

This page was built for publication: A proof of Pyber's base size conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1647396)