Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBijective proofs of shuffle compatibility results
391
0
0.0
(
0
)
Authors
Duff Baker-Jarvis
Ask ChatGPT about the research
No Arabic abstract
Define a permutation to be any sequence of distinct positive integers. Given two permutations p and s on disjoint underlying sets, we denote by p sh s the set of shuffles of p and s (the set of all permutations obtained by interleaving the two permutations). A permutation statistic is a function St whose domain is the set of permutations such that St(p) only depends on the relative order of the elements of p. A permutation statistic is shuffle compatible if the distribution of St on p sh s depends only on St(p) and St(s) and their lengths rather than on the individual permutations themselves. This notion is implicit in the work of Stanley in his theory of P-partitions. The definition was explicitly given by Gessel and Zhuang who proved that various permutation statistics were shuffle compatible using mainly algebraic means. This work was continued by Grinberg. The purpose of the present article is to use bijective techniques to give demonstrations of shuffle compatibility. In particular, we show how a large number of permutation statistics can be shown to be shuffle compatible using a few simple bijections. Our approach also leads to a method for constructing such bijective proofs rather than having to treat each one in an ad hoc manner. Finally, we are able to prove a conjecture of Gessel and Zhuang about the shuffle compatibility of a certain statistic.
rate research
Read More
Consider a permutation p to be any finite list of distinct positive integers. A statistic is a function St whose domain is all permutations. Let S(p,q) be the set of shuffles of two disjoint permutations p and q. We say that St is shuffle compatible if the distribution of St over S(p,q) depends only on St(p), St(q), and the lengths of p and q. This notion is implicit in Stanleys work on P-partitions and was first explicitly studied by Gessel and Zhuang. One of the places where shuffles are useful is in describing the product in the algebra of quasisymmetric functions. Recently Adin, Gessel, Reiner, and Roichman defined an algebra of cyclic quasisymmetric functions where a cyclic version of shuffling comes into play. The purpose of this paper is to define and study cyclic shuffle compatibility. In particular, we show how one can lift shuffle compatibility results for (linear) permutations to cyclic ones. We then apply this result to cyclic descents and cyclic peaks. We also discuss the problem of finding a cyclic analogue of the major index.
The chromatic polynomial and its generalization, the chromatic symmetric function, are two important graph invariants. Celebrated theorems of Birkhoff, Whitney, and Stanley show how both objects can be expressed in three different ways: as sums over all spanning subgraphs, as sums over spanning subgraphs with no broken circuits, and in terms of acyclic orientations with compatible colorings. We establish all six of these expressions bijectively. In fact, we do this with only two bijections, as the proofs in the symmetric function setting are obtained using the same bijections as in the polynomial case and the bijection for broken circuits is just a restriction of the one for all spanning subgraphs.
In this paper we answer a question posed by R. Stanley in his collection of Bijection Proof Problems (Problem 240). We present a bijective proof for the enumeration of walks of length $k$ a chess rook can move along on an $mtimes n$ board starting and ending on the same square.
Let $r(n,k)$ (resp. $s(n,k)$) be the number of Schroder paths (resp. little Schroder paths) of length $2n$ with $k$ hills, and set $r(0,0)=s(0,0)=1$. We bijectively establish the following recurrence relations: begin{align*} r(n,0)&=sumlimits_{j=0}^{n-1}2^{j}r(n-1,j), r(n,k)&=r(n-1,k-1)+sumlimits_{j=k}^{n-1}2^{j-k}r(n-1,j),quad 1le kle n, s(n,0) &=sumlimits_{j=1}^{n-1}2cdot3^{j-1}s(n-1,j), s(n,k) &=s(n-1,k-1)+sumlimits_{j=k+1}^{n-1}2cdot3^{j-k-1}s(n-1,j),quad 1le kle n. end{align*} The infinite lower triangular matrices $[r(n,k)]_{n,kge 0}$ and $[s(n,k)]_{n,kge 0}$, whose row sums produce the large and little Schroder numbers respectively, are two Riordan arrays of Bell type. Hence the above recurrences can also be deduced from their $A$- and $Z$-sequences characterizations. On the other hand, it is well-known that the large Schroder numbers also enumerate separable permutations. This propelled us to reveal the connection with a lesser-known permutation statistic, called initial ascending run, whose distribution on separable permutations is shown to be given by $[r(n,k)]_{n,kge 0}$ as well.
In 2008, Haglund, Morse and Zabrocki formulated a Compositional form of the Shuffle Conjecture of Haglund et al. In very recent work, Gorsky and Negut by combining their discoveries with the work of Schiffmann-Vasserot on the symmetric function side and the work of Hikita and Gorsky-Mazin on the combinatorial side, were led to formulate an infinite family of conjectures that extend the original Shuffle Conjecture of Haglund et al. In fact, they formulated one conjecture for each pair (m,n) of coprime integers. This work of Gorsky-Negut leads naturally to the question as to where the Compositional Shuffle Conjecture of Haglund-Morse-Zabrocki fits into these recent developments. Our discovery here is that there is a compositional extension of the Gorsky-Negut Shuffle Conjecture for each pair (km,kn), with (m,n) co-prime and k > 1.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
