Quasirandom permutations

Series
Graph Theory Seminar
Time
Friday, September 13, 2019 - 11:00am for 1 hour (actually 50 minutes)
Location
Skiles 249
Speaker
Dan Kral – Masaryk University and University of Warwick – http://www.ucw.cz/~kral/index.html.en
Organizer
Xingxing Yu

A combinatorial structure is said to be quasirandom if it resembles a random structure in a certain robust sense. For example, it is well-known that a graph G with edge-density p is quasirandom if and only if the density of C_4 in G is p^4+o(p^4); this property is known to equivalent to several other properties that hold for truly random graphs.  A similar phenomenon was established for permutations: a permutation is quasirandom if and only if the density of every 4-point pattern (subpermutation) is 1/4!+o(1).  We strengthen this result by showing that a permutation is quasirandom if and only if the sum of the densities of eight specific 4-point patterns is 1/3+o(1). More generally, we classify all sets of 4-point patterns having such property.

The talk is based on joint work with Timothy F. N. Chan, Jonathan A. Noel, Yanitsa Pehova, Maryam Sharifzadeh and Jan Volec.