Session I.3 - Graph Theory and Combinatorics
Poster
Complete non-ambiguous trees and associated permutations: connections through the Abelian sandpile model
Haoyue Zhu
Xi'an Jiaotong-Liverpool University, China - This email address is being protected from spambots. You need JavaScript enabled to view it.
Complete non-ambiguous trees (CNATs) were originally introduced by Aval et al. (2014) as a special case of tree-like tableaux. We can associate a permutation to a CNAT by keeping only its leaf dots. In recent work, Chen and Ohlig (2022) initiated the first in-depth combinatorial study of this relationship, notably showing that the number of $n$-permutations that are associated with exactly one CNAT is $2^{n−2}$. We extend this work by enumerating permutations associated with exactly $k$ CNATs for various values of $k \gt 1$, via bijective approaches. Our results rely on a connection to the so-called Abelian sandpile model (see Dukes et al., 2019). We also exhibit a new bijection between $(n−1)$-permutations and CNATs whose permutation is the decreasing permutation $n(n−1)\cdots 1$. This bijection maps the left-to-right minima of the permutation to dots on the bottom row of the corresponding CNAT, and descents of the permutation to empty rows of the CNAT.
References\\ Jean-Christophe Aval, Adrien Boussicault, Mathilde Bouvel, and Matteo Silimbani. Combinatorics of non-ambiguous trees. Adv. App. Math., 56:78–108, 2014.\\ Daniel Chen and Sebastian Ohlig. Associated permutations of complete non-ambiguous trees and Zubieta's conjecture, preprint, 2022.\\ Mark Dukes, Thomas Selig, Jason P. Smith, and Einar Steingrimsson. Permutation graphs and the abelian sandpile model, tiered trees and non-ambiguous binary trees. Electron. J. Comb., 26(3):research paper p3.29, 25, 2019.
Joint work with Thomas Selig (Xi'an Jiaotong-Liverpool University, China).