Orbits onn-tuples for Infinite Permutation Groups

This paper presents a theorem on the growth rate of the orbit-counting sequences of a primitive oligomorphic group: if G is not a highly homogeneous group, then the growth rate for the sequence counting orbits onn -tuples of distinct elements is bounded below by cnn!, wherec ≈ 1.172. The previously known lower bounds concerned all not highly transitive groups, including highly homogeneous groups which are known to have roughly factorial growth rate. This paper shows that highly homogeneous groups are the only groups with such a growth rate, while for all other primitive groups the growth rate is faster and the bound is improved by an exponential factor.