1. Characterization of quasirandom permutations by a pattern sum
- Author
-
Maryam Sharifzadeh, Timothy F. N. Chan, Daniel Král, Jan Volec, Jonathan A. Noel, and Yanitsa Pehova
- Subjects
Sequence ,Mathematics::Combinatorics ,Mathematics::General Mathematics ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,0102 computer and information sciences ,Characterization (mathematics) ,16. Peace & justice ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Set (abstract data type) ,Combinatorics ,Permutation ,Cardinality ,010201 computation theory & mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,QA ,Software ,Mathematics - 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., Appendices 1-5 are contained in the ancillary pdf file available on arXiv for download
- Published
- 2020
- Full Text
- View/download PDF