Permutation groups on unordered sets. I (Q790927)

Let G be a permutation group on a finite or infinite set S and let \(n_ k(G)\) denote the number of orbits when G acts in the usual way on the k- element subsets of S. The paper is concerned with the growth of the sequence \(n_ k\) (whenever these numbers are finite) in terms of the permutation groups induced by G on the subsets of S. For this purpose particular configurations, called arrangements, are introduced and the group action on these arrangements is investigated. When \(O_ 1,...,O_ j,..\) are the orbits of G on the \(\ell\)-element subsets of S for a given \(\ell\), let \(m_ j\) be the number of essentially distinct arrangements inside a set Y belonging to \(O_ j\). The main result states \(\left( \begin{matrix} n_ k\\ \ell -k+1\end{matrix} \right)\leq \sum_{j}m_ j\) whenever G is (k-1)-fold homogeneous and \(\ell \geq k\). Several corollaries are given: For instance \((n_ 3(G))^ 2\leq 13\cdot n_ 4(G)\) provided that G is doubly homogeneous on S. We also obtain an absolute bound for \(n_ 2(G)\) when the action induced on subsets is sufficiently rich.