Séminaire Lotharingien de Combinatoire, 78B.73 (2017), 12 pp.

Ira M. Gessel, Sean Griffin and Vasu Tewari

Schur Positivity and Labeled Binary Trees

Abstract. The first author introduced a multivariate generating function that tracks the distribution of ascents and descents on labeled plane binary trees and conjectured that it was Schur positive. In this article, we give a sketch for a proof of the stronger statement that the generating function restricted to trees with a fixed canopy is Schur positive. Central to our approach is a weighted extension of a bijection of Préville-Ratelle and Viennot relating pairs of paths and binary trees. We apply our results to construct a Sn-action on the regions of the Linial arrangement using a bijection of Bernardi. We then establish the γ-positivity for the distribution of right descents over local binary search trees.


Received: November 14, 2016. Accepted: February 17, 2017. Final version: April 1, 2017.

The following versions are available: