Forcing quasi-randomness in permutations

Jan Volec

Masaryk University

Abstract

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 Rödl, 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.

In 2012, an analogous result was proven for permutations by Kráľ and Pikhurko, who showed that if P is a large permutation where every 4-point permutation has packing density about 1/24, then P is quasi-random (i.e., any fixed k-point permutation has packing density about 1/k! ). It was known before that assuming only the six packing densities of 3-point permutations being about 1/6 does not force P to be quasi-random. In their proof, Kráľ and Pikhurko have used all the 24 packing densities so it was natural to ask how much this list can be reduced. In this talk, we present a set X of eight 4-point permutations such that if the sum of the pattern densities of elements from X in a large permutation P is about |X|/24 , then P is quasi-random. Moreover, we completely characterize all the subsets of S_4 that has this property; it turned out that there are exactly 10 such subsets.

This is joint work with T. Chan, D. Kráľ, Y. Pehova, J. Noel and M. Sharifzadeh.