Talk information

Date: Sunday, December 12, 2021
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Noga Alon (Princeton University and Tel Aviv University)
Title: Martingales, random permutations and $e$

Abstract:

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.