Orbits on \(n\)-tuples for infinite permutation groups (Q5927689)

The author shows that if \(G\) is a primitive permutation group on an infinite set which is not highly homogeneous (so for some \(n\) has more than one orbit on \(n\)-sets) then the number of orbits on \(n\)-tuples of distinct elements is, for large enough \(n\), at least \(c^nn!/p_G(n)\). Here, \(p_G(n)\) is a polynomial depending on \(G\), and the result is proved with the constant \(c\) taking value roughly 1.172; the author shows that \(c\) must take value at most 2. This result greatly improves an earlier bound of the reviewer. The method is inductive on the degree of transitivity. The inductive step is straightforward, and all the work lies in proving the result when \(G\) is not 2-primitive. To start the induction the author considers the cases when \(G\) acts on a graph (when \(G\) is not 2-homogeneous), or a tournament (when \(G\) is 2-homogeneous but not 2-transitive), or a Steiner system (one of the possibilities in the 2-transitive not 2-primitive case). The author finds lower bounds for the numbers of `labelled' substructures of size \(n\) of these structures.