Characterization of quasirandom permutations by a pattern sum
Preprint
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.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- No additional tournaments are quasirandom-forcingEuropean Journal of Combinatorics, 2022
- Tournament Quasirandomness from Local CountingCombinatorica, 2021
- Quasirandom permutations are characterized by 4-point densitiesGeometric and Functional Analysis, 2013
- Quasirandom permutationsJournal of Combinatorial Theory, Series A, 2004
- Hypergraphs, Quasi-randomness, and Conditions for RegularityJournal of Combinatorial Theory, Series A, 2002
- Quasi‐random tournamentsJournal of Graph Theory, 1991
- Quasi‐random hypergraphsRandom Structures & Algorithms, 1990
- Quasi-random graphsCombinatorica, 1989
- On universality of graphs with uniformly distributed edgesDiscrete Mathematics, 1986
- On measures of association and a related problemAnnals of the Institute of Statistical Mathematics, 1970