Characterization of quasirandom permutations by a pattern sum. Issue 4 (27th August 2020)

• Record Type: Journal Article
• Authors: Chan, Timothy F. N.; Král', Daniel; Noel, Jonathan A.; Pehova, Yanitsa; Sharifzadeh, Maryam; Volec, Jan
• Is Part Of: Random structures & algorithms. Volume 57:Issue 4(2020)
• Page Start: 920
• Page End: 939
• Publication Date: 2020-08-27
• Subjects: permutations -- quasirandomness; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20956
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : It is known that a sequence { Π i } i ∈ N of permutations is quasirandom if and only if the pattern density of every 4‐point permutation in Π 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 Π 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.