AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

One consequence of Marcus & Tardos's proof of the Furedi-Hajnal/Stanley-Wilf conjecture is that any n-permutation avoiding a specific k-permutation can be sorted with O_k(n) comparisons. However, no algorithms are known to sort such sequences in O_k(n) time. Chalermsook et al. (2014) and Kozma and Saranurak (2019) proved that two specific sorting algorithms run in O(n 2^{\alpha^{O(k)} n}) time, where \alpha is the inverse-Ackermann function. This time bound reflects a general upper bound on the extremal function of a "light" 0-1 matrix, i.e., one containing exactly one 1 in each column.

In this talk I'll prove that sorting takes n2^{(1+o(1))\alpha} time. The light patterns of Chalermsook et al./Kozma-Saranurak are of the form P x HAT, where P is a permutation matrix, "x" is the Kronecker product, and HAT is the 2x3 "hat" pattern with three 1s. This is essentially the tightest possible bound. We also prove that there is a pattern of this form with extremal function n2^{\alpha}.

Joint work with Parinya Chalermsook and Sorrachai Yingchareonthawornchai.

Roohani Sharma

+49 681 9325 1116

--email hidden

Zoom

527 278 8807

passcode not visible

logged in users only

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.