Algebra & Combinatorics Seminar

Title: Toppleable permutations, excedances and acyclic orientations
Speaker: Arvind Ayyer (IISc Mathematics)
Date: 04 December 2020
Time: 3 pm
Venue: Microsoft Teams (online)

Recall that an \emph{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 of the complete bipartite graph $K_{\lceil n/2 \rceil, \lfloor n/2 \rfloor + 1}$.

This is joint work with P. Tetali (GATech) and D. Hathcock (CMU), and is available at arXiv:2010.11236.

Contact: +91 (80) 2293 2711, +91 (80) 2293 2265 ;     E-mail: chair.math[at]iisc[dot]ac[dot]in
Last updated: 01 Dec 2020