Asymptotic behavior of finite permutation groups acting on subsets.
type: Item
instance of: scholarly article
title: Asymptotic behavior of finite permutation groups acting on subsets.
zbMATH Open document ID: 1086.20003
author: Carmit Benbenisty
author: Aner Shalev
published in: Journal of Algebra
publication date: 2005-06-23T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 20B15
Mathematics Subject Classification ID: 20B35
zbMATH DE Number: 2182058
zbMATH Keywords: finite permutation groups
zbMATH Keywords: primitive permutation groups
zbMATH Keywords: actions on subsets
zbMATH Keywords: large orbit sizes
zbMATH Keywords: alternating groups
zbMATH Keywords: symmetric groups
MaRDI profile type: Publication
full work available at URL: j.jalgebra.2005.02.008
OpenAlex ID: W1978938097
cites work: Influences of variables and threshold intervals under group symmetries
cites work: Finite Permutation Groups and Finite Simple Groups
cites work: The 2-Transitive Permutation Representations of the Finite Chevalley Groups
cites work: Q4882944
cites work: Every monotone graph property has a sharp threshold
DOI: 10.1016/J.JALGEBRA.2005.02.008
description: scientific article; zbMATH DE number 2182058