Quasi-random properties of combinatorial structures such as graphs, hypergraphs or permutations are deterministic conditions that forces a given (deterministic) structure to have ``random-like'' behavior. In the late 1980s, seminal papers of Rodl, Thomason, and Chung, Graham and Wilson initiated a systematic study of properties that forces a large graph to be quasi-random. For example, if a graph $G$ with density $p$ has the correct subgraph densities of all 4-vertex graphs, i.e., the same as a typical random graph $G(n,p)$, then $G$ has the correct subgraph density of any fixed graph.

Graham asked whether a similar phenomenon can be established for permutations, i.e., whether there is an integer $k$ such that if $P$ is a permutation where every $k$-point permutation has packing density about $1/k!$, then $P$ has the correct packing density of any fixed permutation. In 2013, this was answered affirmatively by Kral and Pikhurko, who proved that in fact $k=4$ is sufficient. About 10 years earlier, Cooper observed that $k$ must be at least 4, so their bound on $k$ is best possible. The proof of Kral and Pikhurko utilizes information about all the 24 packing densities of 4-point permutations, so it was natural to ask how much can this list be reduced. In this talk, we present an alternative proof of Kral-Pikhurko theorem that forces the quasi-random behavior of a large permutation using only specific 8 packing densities of 4-point permutations.

This is a joint work with T. Chan, D. Kral and J. Noel.