2013/05/31 by Sergi Elizalde, Martin Rubey
Mathematics · #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Bijection #Combinatorics #Conjecture #Discrete mathematics #Geometry #Homogeneous space #Lattice (music) #Mathematical Dynamics and Fractals #Mathematics #math.CO #msc:05A15 #msc:05A19 #msc:05B35 #msc:05E05 #msc:52C05
paper · pdf · doi:10.1016/j.aim.2015.09.025
published as Adv. Math. 287 (2016), 347-388 · Small typos corrected, and journal reference and grant info added
openalex publication_date 2015/11/20 · arxiv created 2015/11/24 · arxiv updated 2015/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
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ás 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.