Asymptotic behavior of finite permutation groups acting on subsets. (Q556965)

Let a finite permutation group \(G\) act transitively on a set \(\Omega\) of finite size \(n\). Then \(G\) acts naturally on \(P(\Omega)\), the set of all subsets of \(\Omega\). For \(X\in P(\Omega)\) let \(G(X)\) denote the orbit of \(G\) containing \(X\). The main result of the paper is the following Theorem: Let \(n>276\). Suppose \(G\leq S_n\) is primitive and satisfies \(|G(X)|\geq 2n^2\) for all subsets \(X\) of \(\Omega=\{1,\dots,n\}\) such that \(\sqrt n\leq|X|\leq n-\sqrt n\). Then \(G=A_n\) or \(S_n\). The proof makes use of the classification of finite simple groups, the condition \(n>276\) being used to avoid the discussion of doubly-transitive groups having a sporadic socle. There are applications of the Theorem to the study of threshold behavior of monotone Boolean functions which are discussed in the introduction.