Labeled binary trees, subarrangements of the Catalan arrangements, and Schur positivity

DOI10.1016/J.AIM.2019.106814MaRDI QIDQ2326673zbMATH OpenOpenAlexFDO

Authors Ira M. Gessel, Sean Griffin, Vasu V. Tewari

Publication date 10 October 2019

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.03055

ascents-descents hyperplane arrangements labeled trees Schur positivity

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Symmetric functions and generalizations (05E05) Combinatorial aspects of representation theory (05E10) Group actions on combinatorial structures (05E18) Combinatorics of partially ordered sets (06A07)

Abstract: In 1995, the first author introduced a multivariate generating function {

G

} that tracks the distribution of ascents and descents in labeled binary trees. In addition to proving that

G

is symmetric, he conjectured that

G

is Schur positive. We prove this conjecture by expanding

G

positively in terms of ribbon Schur functions. We obtain this expansion using a weight-preserving bijection whose inverse is inspired by the Push-Glide algorithm of Pr'{e}ville-Ratelle and Viennot. In fact, this weight-preserving bijection allows us to establish a stronger version of the first author's conjecture showing that the generating function restricted to labeled binary trees with a fixed canopy is still Schur positive. We also discuss applications in the setting of hyperplane arrangements. We show that a certain specialization of

G

equals the Frobenius characteristic of the natural

m a t h f r a k S_{n}

-action on regions of the semiorder arrangement, which we then expand in terms of {the Frobenius characteristics} of Foulkes characters. We also construct an

m a t h f r a k S_{n}

-action on regions of the Linial arrangement using a set of trees studied by Bernardi, and subsequently compute the character of this action by employing Lagrange inversion. The resulting expression generalizes Postnikov's formula for the number of regions in the Linial arrangement. As a final application, we prove

g a m m a

-nonnegativity for the distribution of the number of right edges over local binary search trees.

Review text

This paper studies the multivariate generating function associated with ascents and descents of labeled plane binary trees. Here, a plane binary tree is a rooted tree in which each internal node can have a left child only, a right child only, or both. For a labeling of the nodes with positive integer labels (where repeated labels are allowed), a left ascent is an edge from a node \(w\) to a left child \(v\) such that the labels \(v^{\ell}\) and \(w^{\ell}\) associated with \(v\) and \(w\) respectively satisfy \(v^{\ell} \leq w^{\ell}\). Otherwise, the edge is called a left descent. Right ascents and right descents are defined analogously. The number of left ascents of a labeled tree \(T\) is denoted by \(\operatorname{lasc}(T)\), and one similarly defines \(\operatorname{rasc}(T)\), \(\operatorname{ldes}(T)\) and \(\operatorname{rdes}(T)\). Let \(x_1,x_2,\ldots\) be commuting indeterminates. With every labeled tree \(T\), associate a monomial \(\mathsf{x}^T\) that is the product of the variables indexed by the node labels. One defines the formal power series \(G\) by \[G = \sum_T \overline{\lambda}^{\operatorname{lasc(T)}} \lambda^{\operatorname{ldes(T)}}\overline{\rho}^{\operatorname{rasc(T)}} \rho^{\operatorname{rdes(T)}} \mathsf{x}^T,\] the sum being over all labeled trees. The first result on this power series is the following functional equation: Theorem. Let \(H(z) = \sum_{n \geq 0} h_n z^n\), where \(h_n\) denotes the \(n\)th complete homogeneous symmetric function. Then \[\frac{(1+\overline{\lambda}G)(1+\overline{\rho}G)}{(1+\lambda G)(1+\rho G)} = H((\overline{\lambda}\overline{\rho} - \lambda \rho)G + \overline{\lambda} + \overline{\rho} - \lambda - \rho).\] Thus \(G\) is a symmetric function. Next, it is shown that \(G\) is Schur positive, thereby also proving a conjecture due to the first author. In fact, an explicit representation of \(G\) is provided showing that it can be expressed as a sum of ribbon Schur functions with coefficients in the semiring \(\mathbb{N}[\overline{\lambda}\overline{\rho},\lambda \rho, \overline{\lambda} + \overline{\rho}, \lambda + \rho]\). Two different proofs for this representation are provided. Moreover, the authors consider trees whose so-called canopy is fixed. It is shown that Schur positivity still holds for the restriction of \(G\) to trees with a given canopy. Specializations of \(G\) for different values of \(\overline{\lambda}\), \(\lambda\), \(\overline{\rho}\) and \(\rho\) are connected to deformations of Coxeter arrangements.

Recommendations

Cites work

Cited in

(8)

Describes a project that uses

Uses Software

OEIS

This page was built for publication: Labeled binary trees, subarrangements of the Catalan arrangements, and Schur positivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2326673)