Quasirandom permutations are characterized by 4-point densities

Daniel Král͏̌, Oleg Pikhurko

Geometric and Functional Analysis · 2013 · 58 citations · 20 references

DOIFull text

Open access

Concepts

Abstract

For permutations $${\pi}$$ and $${\tau}$$ of lengths $${|\pi|\le|\tau|}$$ , let $${t(\pi,\tau)}$$ be the probability that the restriction of $${\tau}$$ to a random $${|\pi|}$$ -point set is (order) isomorphic to $${\pi}$$ . We show that every sequence $${\{\tau_j\}}$$ of permutations such that $${|\tau_j|\to\infty}$$ and $${t(\pi,\tau_j)\to 1/4!}$$ for every 4-point permutation $${\pi}$$ is quasirandom (that is, $${t(\pi,\tau_j)\to 1/|\pi|!}$$ for every $${\pi}$$ ). This answers a question posed by Graham.

References

20