Characterization of quasirandom permutations by a pattern sum

2019/09/24 by Chan, Timothy F. N., Kral, Daniel, Noel, Jonathan A. +3 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1909.11027

Abstract

It is known that a sequence Pi_i of permutations is quasirandom if and only if the pattern density of every 4-point permutation in Pi_i converges to 1/24. We show that there is a set S of 4-point permutations such that the sum of the pattern densities of the permutations from S in the permutations Pi_i converges to |S|/24 if and only if the sequence is quasirandom. Moreover, we are able to completely characterize the sets S with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight.

Cited by

• Lower and Upper Bounds for Small Canonical and Ordered Ramsey Numbers

Related

• Forcing quasirandomness with 4-point permutations
• Quasirandom permutations are characterized by 4-point densities
• Symmetric and Asymptotically Symmetric Permutations
• Quasirandom Permutations
• Quasirandom Arithmetic Permutations