Permutation groups and close-knit families of sets (Q1924977)

This work is motivated by the study of \(m\)-quasi-invariant subsets of a set \(\Omega\) with respect to a group \(G\) of permutations of \(\Omega\). This notion has been introduced by \textit{L. Brailovsky, D. V. Pasechnik} and \textit{C. E. Praeger} [Proc. Am. Math. Soc. 123, No. 8, 2283-2295 (1995; Zbl 0843.20005)]: a subset \(\Gamma\subseteq\Omega\) is called \(m\)-quasi-invariant with respect to \(G\) if \(|\Gamma^g\cap\Gamma|\leq m\) for all \(g\in G\), where \(m\in\mathbb{N}\) is given. One main purpose is to improve a result due to Brailovsky, Pasechnik and Praeger [loc.cit.]: it is shown in Theorem 1.1 that if \(\Gamma\) is an \(m\)-quasi-invariant set for a permutation group \(G\) acting on \(\Omega\) then there exists a \(G\)-invariant subset \(\Delta\) of \(\Omega\) such that the distance \(d(\Gamma,\Delta)\leq 2m-1\), where the (Hamming) distance is the cardinality of the symmetric difference. (Brailovsky, Pasechnik and Praeger had shown in the paper quoted above that \(d(\Gamma,\Delta)\leq f(m)\) for some \(G\)-invariant set \(\Delta\) where \(f\) is a function such that \(f(m)=O(m\log m)\).) The bound obtained in Theorem 1.1 is best possible. It is obtained via considering the more general concept of close-knit families of subsets. A family \(\mathcal F\) of subsets of \(\Omega\) is said to be close-knit (with bound \(m\)) if there is a natural number \(m\) such that \(|\Gamma_1\setminus\Gamma_2|\leq m\) for all \(\Gamma_1,\Gamma_2\in{\mathcal F}\). A structure theorem for arbitrary infinite close-knit families of subsets is the second main purpose of the paper. It is proved in Theorem 3.4 that for such an infinite close-knit family \(\mathcal F\) with bound \(m\) there exists a set \(\Sigma\) such that \(d(\Gamma,\Sigma)\leq 2m-1\) for all \(\Gamma\in{\mathcal F}\) and there is a finite decomposition \({\mathcal F}={\mathcal F}_0\cup{\mathcal F}_1\cup\dots\cup{\mathcal F}_t\) where \({\mathcal F}_0\) is finite and all the other families \({\mathcal F}_i\) are infinite nuclear families. (Here a family \(\mathcal N\) of subsets of \(\Omega\) is said to be nuclear (with parameters \(a,b\in\mathbb{N}\)) if there exists a set \(\Theta\subseteq\Omega\) (the nucleus of \(\mathcal N\)) such that for all \(\Gamma\in\mathcal N\) the equalities \(|\Gamma\setminus\Theta|=a\), \(|\Theta\setminus\Gamma|=b\) hold and \(\bigcap{\mathcal N}\subseteq\Theta\subseteq\bigcup{\mathcal N}\).) In Theorem 4.3 it is shown that a nuclear family has only finitely many different nuclei. In the last section of the paper some related questions are discussed, also concerning families of subgroups and families of vector subspaces instead of families of sets.