Characterization of quasirandom permutations by a pattern sum

DOI10.1002/RSA.20956zbMATH Open1454.05007OpenAlexW3082325971MaRDI QIDQ3386522FDOQ3386522

Authors Timothy F. N. Chan, Jonathan A. Noel, Yanitsa Pehova, Maryam Sharifzadeh, Jan Volec, Daniel Král' 

Publication date 5 January 2021

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.11027

zbMATH Keywords

permutationsquasirandomness

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

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.

Recommendations

• Quasirandom permutations are characterized by 4-point densities
• Quasirandom permutations
• Quasirandom arithmetic permutations
• Lower bound on the size of a quasirandom forcing set of permutations
• Quasirandom Latin squares

Cites Work

• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• A Non-Parametric Test of Independence
• A consistent test of independence based on a sign covariance related to Kendall's tau
• Flag algebras
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Hypergraphs, quasi-randomness, and conditions for regularity
• Limits of permutation sequences
• On measures of association and a related problem
• On the density of transitive tournaments
• On universality of graphs with uniformly distributed edges
• Pseudo-random hypergraphs
• Quasi-Random Set Systems
• Quasi-random graphs
• Quasi-random hypergraphs
• Quasi-random subsets of \(\mathbb{Z}_ n\)
• Quasi-random tournaments
• Quasirandom Groups
• Quasirandom permutations
• Quasirandom permutations are characterized by 4-point densities
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• Tournament quasirandomness from local counting

Cited In (11)

• No additional tournaments are quasirandom-forcing
• Quasirandom arithmetic permutations
• Natural quasirandomness properties
• Quasirandom-Forcing Orientations of Cycles
• Quasirandom permutations
• Forcing generalised quasirandom graphs efficiently
• Lower bound on the size of a quasirandom forcing set of permutations
• Independence of permutation limits at infinitely many scales
• Quasirandom Latin squares
• Density maximizers of layered permutations
• Quasirandom permutations are characterized by 4-point densities

This page was built for publication: Characterization of quasirandom permutations by a pattern sum

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386522)