Cameron's Greedy Conjecture for primitive permutation groups

Let GSym(Ω)G\leqslant\operatorname{Sym}(\Omega) be a finite permutation group. A base for GG is a sequence of points of Ω\Omega with trivial pointwise stabiliser, and b(G)b(G) denotes the minimum size of a base. A greedy base is constructed by choosing each successive point in a longest orbit of the pointwise stabiliser of the previously chosen points; let G(G)\mathcal{G}(G) be the largest size of a greedy base for GG. Cameron's Greedy Conjecture. There is an absolute constant cc such that

G(G)cb(G)\mathcal{G}(G)\leqslant cb(G)

for every finite primitive group GG. The conjecture would improve the general bound G(G)db(G)loglogΩ\mathcal{G}(G)\leqslant db(G)\log\log|\Omega| to a constant-factor bound for primitive groups; it was proposed by Cameron in 1999 and its status is not resolved by the supplied source.

Sources & referencesView supporting material

Primary source

Hong Yi Huang and Colva M. Roney-Dougal, “Greedy bases and relational complexity of diagonal type groups”, arXiv:2605.16032 (2026).

Additional references

3 papers in this index state this conjecture (2024–2026). The statement above is taken from the most recent of them; the others are arXiv:2503.23964, arXiv:2408.14139.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.