Greedy Base Sizes for Uniform-Subset Actions

Definitions and mathematical statement

Let $X$ be a finite set of size $n$, and let $r$ be an integer with $0\le r\le n$. Write \[ \Omega=\binom{X}{r}=\{A\subseteq X:|A|=r\}. \] A permutation group $G\le\operatorname{Sym}(X)$ induces an action on $\Omega$ by $g(A)=\{g(x):x\in A\}$. Let $H\le\operatorname{Sym}(\Omega)$ be the image of this action. For $B\subseteq\Omega$, its pointwise stabilizer is \[ H_{(B)}=\{h\in H:h(A)=A\text{ for every }A\in B\}. \] A base for $H$ is a set $B$ with $H_{(B)}=1$. Passing to the induced image makes this definition faithful; whether the intended source action is assumed faithful must be checked.

For a precise reference convention, a greedy base construction starts with $H_0=H$. Whenever $H_{i-1}\ne1$, choose $A_i\in\Omega$ whose $H_{i-1}$-orbit has maximum cardinality, and put \[ H_i=(H_{i-1})_{A_i}. \] Stop at the first index $k$ with $H_k=1$. Define \[ g_{\max}(H)=\max\{k:k\text{ is the length of such a greedy construction}\}, \] where the maximum includes all choices among tied largest orbits, and the empty construction has length zero when $H=1$. This supplies an explicit possible convention for greedy base size; the extraction does not specify its convention or its treatment of ties.

Extracted problem, with unresolved scope. Determine the greedy base size for the intended standard primitive actions on $\binom{X}{r}$ in the range \[ n<4r^2. \] Under the reference convention above, this would mean determining $g_{\max}(H)$ for the intended family. An action is primitive if it is transitive and its only invariant equivalence relations are equality and the universal relation. The extraction does not identify the acting groups, state unambiguously which action is required to be primitive, or specify the additional restrictions on $n$ and $r$. The elementary conditions $0\le r\le n$ merely make the subset notation meaningful; they do not establish that every such pair is intended. Boundary cases, including singleton subset spaces and complementary subset sizes, remain unspecified.

The retained report passage says that a similar bound is known in most standard uniform-subset cases and that the problem remains open below the displayed threshold. Neither that bound nor the conjecture announced at the end of the passage is supplied. Thus the request to determine an exact value, the reference convention above, and the full family of actions cannot be confirmed from the excerpt. No unique fully quantified conjecture can be recovered from this record alone. The threshold is strictly $n<4r^2$; the equality case is not included in the extracted range.

Short English statement

The record asks for greedy base sizes in certain standard primitive actions on $r$-element subsets of an $n$-element set when $n<4r^2$. It omits the precise group family, the earlier bound, and the announced conjecture. The definitions above provide an explicit reference convention, but the intended numerical statement requires source clarification and human mathematical review.

Sources

• Local supplied UnsolvedMath registry record: permanent ID $30006240$, source problem code catalogue entry, title Greedy Base Sizes for Uniform-Subset Actions; supplied from data/unsolvedmath/problems.json or its supplementary registry catalog/problems.json. The supplied record does not identify which registry file contains this entry.
• Finite Groups, Fusion Systems and Applications (2025), Oberwolfach Reports, pp. 689--752, DOI 10.4171/owr/2025/16. Supplied source URL: https://doi.org/10.4171/owr/2025/16. The background describes Oberwolfach Reports as documenting workshops and their open-problem discussions. The record supplies the year 2025 but no individual proposer.
• Supplied literature-source label: "del Valle workshop report," https://doi.org/10.4171/owr/2025/16. This label is preserved as supplied attribution; it does not independently establish authorship of the extracted problem.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open and says that the exact conjecture is missing, while the standard uniform-subset case below the displayed $4r^2$ threshold remains open. This is supplied dated curation, not independently verified literature assessment. The background explicitly requests independent verification of time-sensitive status and cited claims.
• The retained passage cites "[9, Theorem 2.9]," but supplies neither the corresponding bibliographic entry nor the theorem statement. It also mentions sporadic groups and non-standard groups with alternating socle as context for an ensuing conjecture whose text is absent.
• The registry labels the statement corrected_verified, explaining that only formula delimiters, notation, grammar, and typography were repaired. This supplied editorial label does not establish mathematical correctness or resolve the missing formulation.