Concentration for locally acting permutations (Q1874360): Difference between revisions

For a permutation \(\sigma\) acting on a set \(\Omega\), the set of all points in \(\Omega\) that are not fixed by \(\sigma\) is called the support of \(\sigma\), denoted by supp\((\sigma)\). The degree of a permutation \(\sigma\) is the cardinality of its support, denoted by deg\((\sigma)\). For a nonnegative integer \(l\), we say that a permutation group \(G\) is \(l\)-local if the following holds. For each distinct \(i,j\in \Omega\), if there exists \(\sigma\in G\) with \(\sigma (i)=j\), then there exists \(\tau\in G\) with \(\tau (i)=j\), \(\operatorname {supp}(\tau)\subseteq \operatorname {supp}(\sigma)\) and \(\deg(\tau)\leq 1\). It is proven that for \(G\) being an \(l\)-local group of permutations on \(\Omega\), \(\emptyset \not= A\subseteq G\) and \(\pi\in_U G\), the following holds \[ \text{Prob}(\pi\in A) \text{Exp} \Big(\text{exp} \frac{f(A,\pi)}{8(l^2-2l+2)} \Big) \leq 1, \] where \(f(A,\pi)\) is the squared Talagrand's convex distance between \(A\) and \(\pi\).