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 (δn)~k copies of a specified pattern of length k, for some δ > 0. When n is sufficiently large, and δ is small, the number of these permutations, which we denote by χ_δ~n (γ), satisfies a~nn! ≤ χ_δ~n(γ) ≤ b~nn! where a and b only depend on δ and k.
展开▼
