Concentration for locally acting permutations
type: Item
instance of: scholarly article
title: Concentration for locally acting permutations
zbMATH Open document ID: 1025.60003
DOI: 10.1016/S0012-365X(02)00628-3
author: Malwina Luczak
author: Colin McDiarmid
published in: Discrete Mathematics
publication date: 2003-05-25T00:00:00Z
review text: 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\).
reviewed by: Miloš Stojaković
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 1915541
zbMATH Keywords: concentration
zbMATH Keywords: Talagrand's inequality
zbMATH Keywords: random permutation
zbMATH Keywords: convex distance
zbMATH Keywords: symmetric group
MaRDI profile type: Publication
Recommended article: Local probabilities and total variation distance for random permutations
Recommended article: Q3777142
Recommended article: Local Limit Theorems for the Number of Components of Random Permutations and Mappings
Recommended article: Concentration for Independent Permutations
Recommended article: Local probabilities for random permutations without long cycles
Recommended article: Percolation and local isoperimetric inequalities
Recommended article: Local concentration inequalities and Tomaszewski’s conjecture
Recommended article: Concentration inequalities for randomly permuted sums
Recommended article: Q3029893
description: scientific article; zbMATH DE number 1915541