Greedy bases of primitive permutation groups
Does the greedy algorithm always find a base of a primitive group within a constant factor of the optimum (Cameron)? Is the greedy base size at most 7 for almost simple groups in non-standard actions?
Cite
@misc{cairn-greedy-base-size-primitive-groups,
title = {Greedy bases of primitive permutation groups},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/greedy-base-size-primitive-groups}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY-SA 4.0. Accessed 2026-10-04}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/greedy-base-size-primitive-groups)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task (a literature check, a research direction, a first lemma), and you paste its answer back. A free chatbot and ten minutes are enough; no account is needed to try.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
The question
A base of a permutation group G ≤ Sym(Ω) is a subset B ⊆ Ω whose pointwise stabiliser is trivial; b(G) is the smallest base size. The greedy algorithm builds a base by repeatedly adding a point from a longest orbit of the current stabiliser; the greedy base size is the largest size this procedure can return.
- Cameron's Greedy Conjecture: there is an absolute constant c such that the greedy base size of every finite primitive permutation group is at most c·b(G).
- Conjecture: if G is a finite almost simple primitive group with a non-standard action, its greedy base size is at most 7.
What is known
Equality with b(G) holds for groups with sporadic socle and for primitive groups of odd order; for alternating groups in actions on uniform partitions the greedy size is at most 11·b(G), and for non-standard alternating actions it equals b(G). A 2025 paper proves the conjecture for almost simple groups with alternating socle except actions on r-subsets in a certain range. The main remaining work concerns groups of Lie type.
What counts as progress
- Exhaustive computations over the library of primitive groups (GAP/Magma, degree < 4096): maximal greedy base size versus b(G), with code.
- A counterexample to Conjecture 2: an almost simple group in a non-standard action with a greedy run of length 8 — an explicit sequence of points, each from a longest orbit of the current stabiliser.
- Proofs for families of Lie type.
How it is checked
A greedy run is a certificate: a list of points, with orbit lengths checked at each step, and the final stabiliser trivial. Such a counterexample is machine-checkable (level A).
Source. Posed by Coen del Valle in an extended abstract of the Oberwolfach workshop Finite Groups, Fusion Systems and Applications (2025), recorded in Oberwolfach Reports 16/2025, p. 697 (EMS Press, DOI 10.4171/OWR/2025/16), licensed under CC BY-SA 4.0. This page summarises the problem in our own words; as an adaptation it is shared under CC BY-SA 4.0 as well.