Permutation graphs and the Abelian sandpile model, tiered trees and non-ambiguous binary trees

Dukes, M, Selig, T, Smith, JP ORCID: https://orcid.org/0000-0002-4209-1604 and Steingrímsson, E, 2019. Permutation graphs and the Abelian sandpile model, tiered trees and non-ambiguous binary trees. Electronic Journal of Combinatorics, 26 (3): P3.29. ISSN 1077-8926

Preview

Text 1390769_a2009_Smith.pdf - Post-print Download (285kB) | Preview

Abstract

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. 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., 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, while we also recover results of Perkinson et al. in the case of threshold graphs.

Item Type:	Journal article
Publication Title:	Electronic Journal of Combinatorics
Creators:	Dukes, M., Selig, T., Smith, J.P. and Steingrímsson, E.
Publisher:	Electronic Journal of Combinatorics
Date:	16 August 2019
Volume:	26
Number:	3
ISSN:	1077-8926
Identifiers:	Number Type 10.37236/8225 DOI 1390769 Other
Divisions:	Schools > School of Science and Technology
Record created by:	Linda Sullivan
Date Added:	22 Apr 2021 14:53
Last Modified:	14 Jan 2022 12:48
URI:	https://irep.ntu.ac.uk/id/eprint/42746

Actions (login required)

Edit View

Statistics

Views

Downloads