Quasirandom permutations are characterized by 4-point densities

2012/05/14 by Daniel Král͏̌, Oleg Pikhurko, Král', Daniel +1
Engineering · Mathematics · #05DXX #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · doi:10.48550/arxiv.1205.3074

openalex publication_date 2012/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For permutations P and T of lengths |P|≤|T|, let t(P,T) be the probability that the restriction of T to a random |P|-point set is (order) isomorphic to P. We show that every sequence \T_j\ of permutations such that |T_j|→∞ and t(P,T_j)→ 1/4! for every 4-point permutation P is quasirandom (that is, t(P,T_j)→ 1/|P|! for every P). This answers a question posed by Graham.

Citations

• Limits of permutation sequences through permutation regularity

Related

• Forcing quasirandomness with 4-point permutations
• Characterization of quasirandom permutations by a pattern sum
• Quasirandom Permutations
• Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets
• Symmetric and Asymptotically Symmetric Permutations