On Cameron's Greedy Conjecture

2025/03/31 by del Valle, Coen, Roney-Dougal, Colva M.
#Combinatorics (math.CO) #FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.2503.23964

Abstract

A base for a permutation group G acting on a set Ω is a subset B of Ω whose pointwise stabiliser G_(B) is trivial. There is a natural greedy algorithm for constructing a base of relatively small size. We write G(G) the maximum size of a base it produces, and b(G) for the size of the smallest base for G. In 1999, Peter Cameron conjectured that there exists an absolute constant c such that every finite primitive group G satisfies G(G)≤ cb(G). We show that if G is S_n or A_n acting primitively then either Cameron's Greedy Conjecture holds for G, or G falls into one class of possible exceptions.

Related

• Greedy base sizes for sporadic simple groups
• On Pyber's base size conjecture
• On a generalisation of Cameron's base size conjecture
• A character theoretic formula for base size II
• Base sizes of primitive permutation groups