Characterisation of quasirandom permutations by a pattern sum

3 December 2019
Yanitsa Pehova

Further Information: 

We say that a sequence $\{\Pi_i\}$ of permutations is quasirandom if, for each $k\geq 2$ and each $\sigma\in S_k$, the probability that a uniformly chosen $k$-set of entries of $\Pi_i$ induces $\sigma$ tends to $1/k!$ as $i$ tends to infinity. It is known that a much weaker condition already forces $\{\Pi_i\}$ to be quasirandom; namely, if the above property holds for all $\sigma\in S_4$. We further weaken this condition by exhibiting sets $S\subseteq S_4$, such that if a randomly chosen $k$-set of entries of $\Pi_i$ induces an element of $S$ with probability tending to $|S|/24$, then $\{\Pi_i\}$ is quasirandom. Moreover, we are able to completely characterise the sets $S$ with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight. 
This is joint work with Timothy Chan, Daniel Kráľ, Jon Noel, Maryam Sharifzadeh and Jan Volec.

  • Combinatorial Theory Seminar