Characterization of quasirandom permutations by a pattern sum

DOI10.1002/RSA.20956zbMATH Open1454.05007arXiv1909.11027OpenAlexW3082325971MaRDI 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)

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.

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

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

zbMATH Keywords

permutationsquasirandomness

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cites Work

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

Cited In (10)

• 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

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)