A proof of Pyber's base size conjecture

DOI10.1016/J.AIM.2018.04.009zbMATH Open1428.20005arXiv1611.09487OpenAlexW2558482094WikidataQ123005683 ScholiaQ123005683MaRDI QIDQ1647396FDOQ1647396

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)

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|$.

Full work available at URL: https://arxiv.org/abs/1611.09487

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

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)

Cites Work

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

Cited In (25)

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

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)