Combinatorics of Permutations

Graphs, Hypergraphs, and Computing

27 March 14:00 - 15:00

Jacob Fox - Massachusetts Institute of Technology, MIT

For a permutation p, let S_n(p) be the number of permutations on letters avoiding p. A decade ago, Marcus and Tardos proved the celebrated Stanley-Wilf conjecture that, for each permutation p, S_n(p)^{1/n} tends to a finite limit L(p). Backed by numerical evidence, it has been conjectured by various researchers over the years that L(p) is on the order of k^2 for every permutation p on k letters. We disprove this conjecture, showing that L(p) is exponential in a power of k for almost all permutations p on k letters. The proof uses ideas from extremal and probabilistic combinatorics.
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