Tiered trees, weights, and q-Eulerian numbers

William Dugan, Sam Glennon, Paul E. Gunnells, Einar Steingrimsson

Research output: Contribution to journalArticle

Abstract

Maxmin trees are labeled trees with the property that each vertex is either a local maximum or a local minimum. Such trees were originally introduced by Postnikov [12], who gave a formula to count them and different combinatorial interpretations for their number. In this paper we generalize this construction and define tiered trees by allowing more than two classes of vertices. Tiered trees arise naturally when counting the absolutely indecomposable representations of certain quivers, and also when one enumerates torus orbits on certain homogeneous varieties. We define a notion of weight for tiered trees and prove bijections between various weight 0 tiered trees and other combinatorial objects; in particular order n weight 0 maxmin trees are naturally in bijection with permutations on n−1 letters. We conclude by using our weight function to define a new q-analogue of the Eulerian numbers.

LanguageEnglish
Pages24-49
Number of pages26
JournalJournal of Combinatorial Theory Series A
Volume164
Early online date18 Dec 2018
DOIs
Publication statusPublished - 31 May 2019

Fingerprint

Eulerian numbers
Orbits
Bijection
Labeled Trees
Quiver
Q-analogue
Local Minima
Weight Function
Counting
Torus
Count
Permutation
Orbit
Generalise
Vertex of a graph

Keywords

  • maxmin trees
  • permutations
  • nonambiguous trees
  • q-Eulerian numbers
  • Eulerian numbers
  • intransitive trees

Cite this

Dugan, William ; Glennon, Sam ; Gunnells, Paul E. ; Steingrimsson, Einar. / Tiered trees, weights, and q-Eulerian numbers. In: Journal of Combinatorial Theory Series A . 2019 ; Vol. 164. pp. 24-49.
@article{347bc388e3b445a5bc778115a082f012,
title = "Tiered trees, weights, and q-Eulerian numbers",
abstract = "Maxmin trees are labeled trees with the property that each vertex is either a local maximum or a local minimum. Such trees were originally introduced by Postnikov [12], who gave a formula to count them and different combinatorial interpretations for their number. In this paper we generalize this construction and define tiered trees by allowing more than two classes of vertices. Tiered trees arise naturally when counting the absolutely indecomposable representations of certain quivers, and also when one enumerates torus orbits on certain homogeneous varieties. We define a notion of weight for tiered trees and prove bijections between various weight 0 tiered trees and other combinatorial objects; in particular order n weight 0 maxmin trees are naturally in bijection with permutations on n−1 letters. We conclude by using our weight function to define a new q-analogue of the Eulerian numbers.",
keywords = "maxmin trees, permutations, nonambiguous trees, q-Eulerian numbers, Eulerian numbers, intransitive trees",
author = "William Dugan and Sam Glennon and Gunnells, {Paul E.} and Einar Steingrimsson",
year = "2019",
month = "5",
day = "31",
doi = "10.1016/j.jcta.2018.12.002",
language = "English",
volume = "164",
pages = "24--49",
journal = "Journal of Combinatorial Theory Series A",
issn = "0097-3165",

}

Tiered trees, weights, and q-Eulerian numbers. / Dugan, William; Glennon, Sam; Gunnells, Paul E.; Steingrimsson, Einar.

In: Journal of Combinatorial Theory Series A , Vol. 164, 31.05.2019, p. 24-49.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Tiered trees, weights, and q-Eulerian numbers

AU - Dugan, William

AU - Glennon, Sam

AU - Gunnells, Paul E.

AU - Steingrimsson, Einar

PY - 2019/5/31

Y1 - 2019/5/31

N2 - Maxmin trees are labeled trees with the property that each vertex is either a local maximum or a local minimum. Such trees were originally introduced by Postnikov [12], who gave a formula to count them and different combinatorial interpretations for their number. In this paper we generalize this construction and define tiered trees by allowing more than two classes of vertices. Tiered trees arise naturally when counting the absolutely indecomposable representations of certain quivers, and also when one enumerates torus orbits on certain homogeneous varieties. We define a notion of weight for tiered trees and prove bijections between various weight 0 tiered trees and other combinatorial objects; in particular order n weight 0 maxmin trees are naturally in bijection with permutations on n−1 letters. We conclude by using our weight function to define a new q-analogue of the Eulerian numbers.

AB - Maxmin trees are labeled trees with the property that each vertex is either a local maximum or a local minimum. Such trees were originally introduced by Postnikov [12], who gave a formula to count them and different combinatorial interpretations for their number. In this paper we generalize this construction and define tiered trees by allowing more than two classes of vertices. Tiered trees arise naturally when counting the absolutely indecomposable representations of certain quivers, and also when one enumerates torus orbits on certain homogeneous varieties. We define a notion of weight for tiered trees and prove bijections between various weight 0 tiered trees and other combinatorial objects; in particular order n weight 0 maxmin trees are naturally in bijection with permutations on n−1 letters. We conclude by using our weight function to define a new q-analogue of the Eulerian numbers.

KW - maxmin trees

KW - permutations

KW - nonambiguous trees

KW - q-Eulerian numbers

KW - Eulerian numbers

KW - intransitive trees

UR - https://www.journals.elsevier.com/journal-of-combinatorial-theory-series-a

UR - https://arxiv.org/abs/1702.02446v3

U2 - 10.1016/j.jcta.2018.12.002

DO - 10.1016/j.jcta.2018.12.002

M3 - Article

VL - 164

SP - 24

EP - 49

JO - Journal of Combinatorial Theory Series A

T2 - Journal of Combinatorial Theory Series A

JF - Journal of Combinatorial Theory Series A

SN - 0097-3165

ER -