Quasirandomness of permutations

Graphs, Hypergraphs, and Computing

25 February 14:00 - 15:00

Daniel Kral - University of Warwick

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. We associate every sequence of permutations with a measure on a unit square and show the following: if the density of every 4-point subpermutation in a permutation p is 1/4!+o(1), then the density of every k-point subpermutation is 1/k!+o(1). This answers a question of Graham whether quasirandomness of a permutation is captured by densities of its 4-point subpermutations.

The result is based on a joint work with Oleg Pikhurko.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to