Orbital maximin problem

From Groupprops
Jump to: navigation, search

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