Toppleable Permutations, Ursell Functions and Excedances

Combinatorics Seminar
Friday, October 16, 2020 - 10:00am for 1 hour (actually 50 minutes)
Bluejeans link: (To receive the password, please email Lutz Warnke)
Arvind Ayyer – Indian Institute of Science, Bengaluru, India –
Prasad Tetali

 Recall that an excedance of a permutation $\pi$ is any position $i$
 such that $\pi_i > i$. Inspired by the work of Hopkins, McConville and
 Propp (arXiv:1612.06816) on sorting using toppling, we say that
 a permutation is toppleable if it gets sorted by a certain sequence of
 toppling moves. For the most part of the talk, we will explain the
 main ideas in showing that the number of toppleable permutations on n
 letters is the same as those for which excedances happen exactly at
 $\{1,\dots, \lfloor (n-1)/2 \rfloor\}$. Time permitting, we will give
 some ideas showing that this is also the number of acyclic
 orientations with unique sink (also known as the Ursell function) of the
 complete bipartite graph $K_{\lceil n/2 \rceil, \lfloor n/2 \rfloor + 1}$.

 This is joint work with D. Hathcock (CMU) and P. Tetali (Georgia Tech).