Department of

Mathematics


Seminar Calendar
for events the day of Tuesday, June 30, 2020.

     .
events for the
events containing  

(Requires a password.)
More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
       May 2020              June 2020              July 2020      
 Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu 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    5  6  7  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

2:00 pm in Zoom,Tuesday, June 30, 2020

Variations on twins in permutations

Andrzej Dudek (Western Michigan University)

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