# Orbital maximin problem

## Statement

For a given natural number $n$ and a group property $\alpha$, the orbital maximin problem for the pair $(n,\alpha)$ is the problem of finding a group $G$ satisfying $\alpha$ with an action on a set of size $n$ such that the minimum of the sizes of the orbitals under the action of $G$ is as large as possible.

Here, an orbital is an orbit under the induced action of $G$ on unordered pairs of distinct elements from the set.

In general, we take $\alpha$ to be a property that is both subgroup-closed and quotient-closed. For such $\alpha$, we can restrict attention to faithful group actions.

This is related to the orbital maximax problem, where we try to maximize the size of the largest orbital.

## Particular cases

### Exact values and conditional exact values

Group property/constraint on action Value for orbital maximin Proof
cyclic group $n$ follows from orbital maximin equals size of set for abelian groups
abelian group $n$ orbital maximin equals size of set for abelian groups
nilpotent group $n$ orbital maximin equals size of set for nilpotent groups
Group with nontrivial center acting faithfully $n$ orbital maximin equals size of set for faithful actions by groups with nontrivial center
solvable group $n(n-1)$ iff $n$ is a prime power orbital maximin equals number of ordered pairs of distinct elements for solvable groups iff size is prime power
group satisfying Oliver's condition $n(n - 1)$ iff $n$ is a prime power (see above)
metabelian group $n(n - 1)$ iff $n$ is a prime power (see above)

### Bounds

Group property/constraint on action Bound for orbital maximin Proof/discussion
solvable group bounded below by a constant times $n(n - 1)$ orbital maximin is bounded below by constant fraction of number of ordered pairs of distinct elements for solvable groups
metabelian group bounded below by a constant times $n(n - 1)$ (see above)
group satisfying Oliver's condition bounded below at least by $\Omega(n \log n)$, probably $\Omega(n^2)$ orbital maximin problem for groups satisfying Oliver's condition