Geodesic
Permutation graphs and the abelian sandpile model, tiered trees and non-ambiguous binary trees
Mark Dukes1 ; Thomas Selig2 ; Jason P. Smith3 ; Einar Steingrímsson4
1University College Dublin
2University of Iceland
3University of Aberdeen
4University of Strathclyde
The electronic journal of combinatorics, Tome 26 (2019) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A permutation graph is a graph whose edges are given by inversions of a permutation. We study the Abelian sandpile model (ASM) on such graphs. We exhibit a bijection between recurrent configurations of the ASM on permutation graphs and the tiered trees introduced by Dugan et al. [10]. This bijection allows certain parameters of the recurrent configurations to be read on the corresponding tree. In particular, we show that the level of a recurrent configuration can be interpreted as the external activity of the corresponding tree, so that the bijection exhibited provides a new proof of a famous result linking the level polynomial of the ASM to the ubiquitous Tutte polynomial. We show that the set of minimal recurrent configurations is in bijection with the set of complete non-ambiguous binary trees introduced by Aval et al. [2], and introduce a multi-rooted generalization of these that we show to correspond to all recurrent configurations. In the case of permutations with a single descent, we recover some results from the case of Ferrers graphs presented in [11], while we also recover results of Perkinson et al. [16] in the case of threshold graphs.
DOI : 10.37236/8225
Classification : 05C05, 82C20

Mark Dukes  1   ; Thomas Selig  2   ; Jason P. Smith  3   ; Einar Steingrímsson  4

1 University College Dublin
2 University of Iceland
3 University of Aberdeen
4 University of Strathclyde 
@article{10_37236_8225,
     author = {Mark Dukes and Thomas Selig and Jason P. Smith and Einar Steingr{\'\i}msson},
     title = {Permutation graphs and the abelian sandpile model, tiered trees and non-ambiguous binary trees},
     journal = {The electronic journal of combinatorics},
     year = {2019},
     volume = {26},
     number = {3},
     doi = {10.37236/8225},
     zbl = {1418.05051},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8225/}
}
TY  - JOUR
AU  - Mark Dukes
AU  - Thomas Selig
AU  - Jason P. Smith
AU  - Einar Steingrímsson
TI  - Permutation graphs and the abelian sandpile model, tiered trees and non-ambiguous binary trees
JO  - The electronic journal of combinatorics
PY  - 2019
VL  - 26
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8225/
DO  - 10.37236/8225
ID  - 10_37236_8225
ER  - 
%0 Journal Article
%A Mark Dukes
%A Thomas Selig
%A Jason P. Smith
%A Einar Steingrímsson
%T Permutation graphs and the abelian sandpile model, tiered trees and non-ambiguous binary trees
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/8225/
%R 10.37236/8225
%F 10_37236_8225
Mark Dukes; Thomas Selig; Jason P. Smith; Einar Steingrímsson. Permutation graphs and the abelian sandpile model, tiered trees and non-ambiguous binary trees. The electronic journal of combinatorics, Tome 26 (2019) no. 3. doi: 10.37236/8225

Cité par Sources :