Six Permutation Patterns Force Quasirandomness

• Published in: Discrete analysis 2024-10
• Main Authors: Gabriel Crudele, Peter Dukes, Jonathan A. Noel
• Format: Article
• Language: English
• ISSN: 2397-3129
• DOI: 10.19086/da.122973

Six permutation patterns force quasirandomness, Discrete Analysis 2024:8, 26 pp. Quasirandomness is a major theme in combinatorics, with several important applications. The broad idea is to say that a combinatorial structure is quasirandom if it has important properties that a random structure of the same type will have with high probability. And what turns this idea from a source of possible definitions into a theory with applications is that it often turns out that quite different-looking properties are equivalent. For example, the following three properties of a graph with $n$ vertices and density $\alpha$ are equivalent (up to adjustments to the error terms). 1. The number of quadruples $(x,y,z,w)$ such that $xy, yz, zw$ and $wx$ are edges of $G$ is approximately $\alpha^4n^4$. 1. For every small graph $H$ with $k$ vertices, the number of functions $f:V(H)\to V(G)$ such that $f(x)f(y)$ is an edge of $G$ for every edge $xy$ of $H$ is approximately $\alpha^{|E(H)|}n^k$. 1. For every set $X$ of vertices of $G$, the number of edges $xy$ with $x,y\in X$ differs from $\alpha\binom{|X|}2$ by at most a small multiple of $n^2$. The fact that the first property implies the third is particularly useful because often it is easier to verify the first but also easier to deduce consequences from the third. The theory of quasirandom graphs was developed by Thomason and by Chung, Graham and Wilson. Later, similar equivalences were discovered for other combinatorial structures, such as hypergraphs and subsets of finite Abelian groups. This paper is about a notion of quasirandomness for permutations, originally introduced by Joshua Cooper. As with graphs, it can be defined in several equivalent ways. One central property of a permutation $\pi$ of $\{1,2,\dots,n\}$ is known as _balance_: we say that $\pi$ is balanced if for every pair of intervals $I$ and $J$, $$|I\cap\pi(J)|-|I||J|/n|$$ is at most a small multiple of $n$. That is, $\pi$ spreads every interval out so that it is evenly distributed in $\{1,2,\dots,n\}$. Another, more relevant to this paper, concerns permutation patterns. Given some fixed permutation $\sigma$ of $\{1,2,\dots,k\}$, we say that $\sigma$ _occurs in_ $\pi$ _at_ $(x_1,\dots,x_k)$ if $x_1