Symmetries of statistics on lattice paths between two boundaries

DOI10.1016/J.AIM.2015.09.025MaRDI QIDQ895545zbMATHOpenAlexFDO

Authors Sergi Elizalde, Martin Rubey

Publication date 3 December 2015

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

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

zbMATH Keywords

triangulationlattice pathbijectionmatroidTutte polynomialcombinatorial statisticsemistandard Young tableauflagged tableau

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Graph polynomials (05C31) Symmetric functions and generalizations (05E05) Combinatorial aspects of representation theory (05E10) Combinatorial identities, bijective combinatorics (05A19) Combinatorial aspects of matroids and geometric lattices (05B35) Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05)

Abstract: We prove that on the set of lattice paths with steps N=(0,1) and E=(1,0) that lie between two fixed boundaries T and B (which are themselves lattice paths), the statistics `number of E steps shared with B' and `number of E steps shared with T' have a symmetric joint distribution. To do so, we give an involution that switches these statistics, preserves additional parameters, and generalizes to paths that contain steps S=(0,-1) at prescribed x-coordinates. We also show that a similar equidistribution result for path statistics follows from the fact that the Tutte polynomial of a matroid is independent of the order of its ground set. We extend the two theorems to k-tuples of paths between two boundaries, and we give some applications to Dyck paths, generalizing a result of Deutsch, to watermelon configurations, to pattern-avoiding permutations, and to the generalized Tamari lattice. Finally, we prove a conjecture of Nicol'as about the distribution of degrees of k consecutive vertices in k-triangulations of a convex n-gon. To achieve this goal, we provide a new statistic-preserving bijection between certain k-tuples of non-crossing paths and k-flagged semistandard Young tableaux, which is based on local moves reminiscent of jeu de taquin.

Recommendations

• scientific article; zbMATH DE number 7058738
• Lattice path matroids: Enumerative aspects and Tutte polynomials
• Bijections for pairs of non-crossing lattice paths and walks in the plane
• The degree of symmetry of lattice paths
• A uniformly distributed statistic on a class of lattice paths

Cites work

• scientific article; zbMATH DE number 3113838 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1058044 (Why is no real title available?)
• scientific article; zbMATH DE number 3086778 (Why is no real title available?)
• A Contribution to the Theory of Chromatic Polynomials
• A bijection between 2-triangulations and pairs of non-crossing Dyck paths
• A bijection on Dyck paths and its consequences
• A generalization of diagonal flips in a convex polygon
• An involution on Dyck paths and its consequences
• Another bijection between 2-triangulations and pairs of non-crossing Dyck paths
• Basic analytic combinatorics of directed lattice paths
• Binomial determinants, paths, and hook length formulae
• Conjectured statistics for the higher \(q,t\)-Catalan sequences
• Flagged Schur functions, Schubert polynomials, and symmetrizing operators
• Generalized triangulations and diagonal-free subsets of stack polyominoes
• Higher trivariate diagonal harmonics via generalized Tamari posets
• Lattice path matroids: Enumerative aspects and Tutte polynomials
• Lost (and Found) in Translation: André's Actual Method and Its Application to the Generalized Ballot Problem
• Maximal fillings of Moon polyominoes, simplicial complexes, and Schubert polynomials
• On line arrangements in the hyperbolic plane
• On the enumeration and generation of generalized Dyck words
• Return polynomials for non-intersecting paths above a surface on the directed square lattice
• Simple formulas for lattice paths avoiding certain periodic staircase boundaries
• Strong versions of Sperner's theorem
• Symmetries of statistics on lattice paths between two boundaries
• Tableau switching: Algorithms and applications
• The Catalan matroid
• The Tutte polynomial
• The \(q,t\)-Catalan numbers and the space of diagonal harmonics. With an appendix on the combinatorics of Macdonald polynomials
• The number of intervals in the \(m\)-Tamari lattices
• The number of lattice paths below a cyclically shifting boundary
• 𝑎𝑑-nilpotent 𝔟-ideals in 𝔰𝔩(𝔫) having a fixed class of nilpotence: combinatorics and enumeration

Cited in

(11)

• Quarter-plane lattice paths with interacting boundaries: the Kreweras and reverse Kreweras models
• Symmetries of statistics on lattice paths between two boundaries
• Descent sets on 321-avoiding involutions and hook decompositions of partitions
• A dominance result for self-dual lattice paths and applications
• Bijections for pairs of non-crossing lattice paths and walks in the plane
• Bijections for Weyl chamber walks ending on an axis, using arc diagrams and Schnyder woods
• Bijections for walks ending on an axis, using open arc diagrams
• The degree of symmetry of lattice paths
• Standard complexes of matroids and lattice paths
• Some statistics on generalized Motzkin paths with vertical steps
• An involution on Dyck paths that preserves the rise composition and interchanges the number of returns and the position of the first double fall

This page was built for publication: Symmetries of statistics on lattice paths between two boundaries

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