Six Permutation Patterns Force Quasirandomness

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$.
2. 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$.
3. 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<\dots<x_k$ and the map that takes $\sigma(i)$ to $\pi(x_i)$, for $1\leq i\leq k$, is order preserving. In other words, we require that $\pi(x_i)<\pi(x_j)$ if and only if $\sigma(i)<\sigma(j)$. The density of $\sigma$ in $\pi$ is the probability that $\sigma$ occurs in $\pi$ at $(x_1,\dots,x_k)$ if we choose the increasing sequence $(x_1,\dots,x_k)$ uniformly at random from all such sequences. For a random permutation $\pi$ we would expect this density to be roughly $1/k!$, and this is the basis for a quasirandomness definition. Loosely speaking, we say that $\pi$ is quasirandom if all small permutations have approximately the right density in $\pi$.

From the discussion above for graphs, we see that if a graph has roughly the same number of edges and 4-cycles as a random graph of the same density, then it is quasirandom. One can ask whether something similar is true for permutations: that is, is there some finite set $\Sigma$ of permutations such that if $\pi$ is some permutation of $\{1,2,\dots,n\}$ and the density of $\sigma$ in $\pi$ is approximately correct for every $\sigma\in\Sigma$ (that is, it is approximately $1/k!$ if $\sigma$ permutes $k$ objects), then $\pi$ is quasirandom? In other words, is there a finite set of permutations such that if all of those occur with the correct density, then in fact every permutation (of fixed size as $n$ tends to infinity) occurs with the correct density? In such a situation, we say that $\Sigma$ forces quasirandomness.

This question was answered affirmatively by Král and Pikhurko, who showed that $S_4$ forces quasirandomness: that is, if every permutation of four objects occurs in $\pi$ with density roughly $1/24$, then every small permutation occurs with roughly its correct density.

A further result was proved by Bergsma and Dassios that strengthened this one in two ways. First, it showed that there was a set $\{\sigma_1,\dots,\sigma_8\}$ of only eight of the 24 permutations in $S_4$ that was already sufficient to force quasirandomness. But secondly, it showed that one did not have to assume that each $\sigma_i$ occurred with density roughly 1/24: it was enough to assume merely that a certain weighted average of the densities was roughly 1/24.

There are two obvious questions to ask at this point. One is the minimal number of permutations needed to force quasirandomness, and the other is the minimum number of permutations needed for some weighted average of their densities to force quasirandomness.

For both questions, the best known lower bound was 4, by a result of Kurečka, and the result just mentioned gave an upper bound of 8. This paper proves an upper and lower bound of 6 for the second question, the one about weighted averages, so that question is completely settled, and the bounds for the first question are now between 4 and 6. The permutations that provide the upper bound are 123, 321, 2143, 3412, 2413 and 3142, where the first four have weight 1 and the last two have weight 1/2. (This gives a weighted sum rather than a weighted average, but the normalizing factor is irrelevant. Here we are writing $a_1\dots a_k$ for the permutation of $\{1,2,\dots,k\}$ that takes $i$ to $a_i$.)

The proof that this linear combination of permutation densities forces quasirandomness is not at all straightforward: it involves exhibiting two linear combinations of a large number of objects called rooted permutons, and then verifying that each coordinate of an associated vector with 720 entries is equal to 11/24. The verification could in principle be done by hand (though the authors sensibly did not do it that way) but finding the linear combinations in the first place would be almost impossible without computer assistance: flag algebras were used to reduce the problem to a semidefinite programming question, which was fed to an SDP solver.

The proof of the accompanying lower bound (which amounts to showing that a linear combination of five permutation densities will never force quasirandomness) is not easy either. It is mainly theoretical, but it too involves computer assistance in one or two places.

The paper ends with three open problems, one of which is a conjecture that the linear combination of six permutations discovered by the authors is unique up to a non-zero scalar multiple.