Department of

May 2020 June 2020July 2020Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa SuMoTu We Th Fr Sa 1 2 1 2 3 4 5 6 1 2 3 4 3 4 5 6 7 8 9 7 8 9 10 11 12 13 567 8 9 10 11 10 11 12 13 14 15 16 14 15 16 17 18 19 20 12 13 14 15 16 17 18 17 18 19 20 21 22 23 21 22 23 24 25 26 27 19 20 21 22 23 24 25 24 25 26 27 28 29 30 28 29 30 26 27 28 29 30 31 31

Tuesday, June 30, 2020

**Abstract:** Let $\pi$ be a permutation of the set $[n]=\{1,2,\dots, n\}$. Two disjoint order-isomorphic subsequences of $\pi$ are called twins. How long twins are contained in every permutation? The well known Erdos-Szekeres theorem implies that there is always a pair of twins of length $\Omega(\sqrt{n})$. On the other hand, by a simple probabilistic argument Gawron proved that for every $n\geq 1$ there exist permutations with no twins of length greater than $O(n^{2/3})$. His conjecture states that the latter bound is the correct size of the longest twins guaranteed in every permutation. In this talk we show that asymptotically almost surely a random permutation contains twins of length at least $\Omega(n^{2/3})$, which supports this conjecture. (This was also proved recently by Bukh and Rudenko.) We also discuss several variants of the problem with diverse restrictions imposed on the twins.

This is a joint work with Jaroslaw Grytczuk and Andrzej Rucinski.

For the Zoom ID, please email Sean at SEnglish (at) illinois (dot) edu