Quasirandomness of permutations

Graph Theory Seminar
Thursday, April 18, 2013 - 12:05pm for 1 hour (actually 50 minutes)
Skiles 005
Daniel Kral – University of Warwick
Robin Thomas
A systematic study of large combinatorial objects has recently led to discovering many connections between discrete mathematics and analysis. In this talk, we apply analytic methods to permutations. In particular, we associate every sequence of permutations with a measure on a unit square and show the following: if the density of every 4-element subpermutation in a permutation p is 1/4!+o(1), then the density of every k-element subpermutation is 1/k!+o(1). This answers a question of Graham whether quasirandomness of a permutation is captured by densities of its 4-element subpermutations. The result is based on a joint work with Oleg Pikhurko.