Speaker: Jan Volec
Title: Forcing quasi-randomness in permutations
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 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, Y. Pehova and M. Sharifzadeh