A viewpoint for permutations with a low density of patterns

Analyzing block partitions of permutation matrices has proven useful in studying permutations with a low density of patterns. Conditioning on the size and density of various blocks provides a large amount of control on both the number and type of patterns that can exist globally in a permutation. Using this technique, we provide a bound for the number of permutations with a low density of patterns, and a strengthening of the pattern removal lemma in a similar vein to to Szemerédi’s removal lemma for graphs. The term “low density” refers to permutations in $S_n$ containing fewer than ${(\delta n)}^k$ copies of a specified pattern of length $k$, for some $\delta \gt 0$. When $n$ is sufficiently large, and $\delta$ is small, the number of these permutations, which we denote by $\chi^n_{\delta} (\gamma)$, satisfies\[a^n n ! \leq \chi^n_{\delta} (\gamma) \leq b^n n !\]where $a$ and $b$ only depend on $\delta$ and $k$.

2010 Mathematics Subject Classification

Primary 05A05. Secondary 05D05.

Full Text (PDF format)

Published 20 March 2015