TAU Combinatorics Seminar 2021/22

When: Sunday December 12, 10am
Where: Schreiber 309
Speaker: Noga Alon, Princeton University and Tel Aviv University
Title: Martingales, random permutations and $e$


I will describe two recent results dealing with random permutations.

The first, obtained jointly with Defant and Kravitz, determines the limit shape of the typical scaled graph of a permutation of $[n]$ obtained from a uniform random permutation by sorting the ascending runs in an increasing order of their first elements. This settles a conjecture of Alexandersson and Nabawanda.

The second deals with the following random process. Let $(\sigma_1,\sigma_2, ... ,\sigma_n)$ be a uniform random permutation of $[n]$. Starting with $S=\{0\}$, the elements $\sigma_i$ join $S$ one by one, in order. When an entering element is larger than the current minimum element of $S$, this minimum leaves S. The question addressed is the typical size of $S$ at the end of the process. I will describe the answer, confirming a recent conjecture of Georgiou, Katkov and Tsodyks suggested by simulations and by a heuristic argument.

Martingale concentration plays a crucial role in both results, and the number $e=2.718281828...$ appears in both.