Sweep maps: a continuous family of sorting algorithms
From MaRDI portal
Abstract: We define a family of maps on lattice paths, called sweep maps, that assign levels to each step in the path and sort steps according to their level. Surprisingly, although sweep maps act by sorting, they appear to be bijective in general. The sweep maps give concise combinatorial formulas for the q,t-Catalan numbers, the higher q,t-Catalan numbers, the q,t-square numbers, and many more general polynomials connected to the nabla operator and rational Catalan combinatorics. We prove that many algorithms that have appeared in the literature (including maps studied by Andrews, Egge, Gorsky, Haglund, Hanusa, Jones, Killpatrick, Krattenthaler, Kremer, Orsina, Mazin, Papi, Vaille, and the present authors) are all special cases of the sweep maps or their inverses. The sweep maps provide a very simple unifying framework for understanding all of these algorithms. We explain how inversion of the sweep map (which is an open problem in general) can be solved in known special cases by finding a "bounce path" for the lattice paths under consideration. We also define a generalized sweep map acting on words over arbitrary alphabets with arbitrary weights, which is also conjectured to be bijective.
Recommendations
Cites work
- scientific article; zbMATH DE number 1405591 (Why is no real title available?)
- A Schröder generalization of Haglund's statistic on Catalan paths
- A conjectured combinatorial formula for the Hilbert series for diagonal harmonics
- A continuous family of partition statistics equidistributed with length
- A proof of the \(q,t\)-Catalan positivity conjecture
- A proof of the \(q,t\)-square conjecture
- A remarkable \(q,t\)-Catalan sequence and \(q\)-Lagrange inversion
- An explanatory bijection of some remarkable properties of bridges
- Compactified Jacobians and q,t-Catalan numbers. I.
- Compactified Jacobians and \(q,t\)-Catalan numbers. II
- Conjectured statistics for the q,t-Catalan numbers.
- Conjectured statistics for the higher \(q,t\)-Catalan sequences
- Identities and positivity conjectures for some remarkable operators in the theory of symmetric functions
- Lattice diagram polynomials and extended Pieri rules
- Rational parking functions and Catalan numbers
- Results and conjectures on simultaneous core partitions
- Square $\boldsymbol {q,t}$-lattice paths and $\boldsymbol {\nabla (p_n)}$
- Sweep maps for lattice paths (extended abstract)
- Trapezoidal lattice paths and multivariate analogues
- 𝑎𝑑-nilpotent 𝔟-ideals in 𝔰𝔩(𝔫) having a fixed class of nilpotence: combinatorics and enumeration
Cited in
(24)- The steep-bounce zeta map in parabolic Cataland
- Rational parking functions and Catalan numbers
- Rational Dyck paths in the non relatively prime case
- Dinv, area, and bounce for \(\overrightarrow{k} \)-Dyck paths
- Sweep maps for lattice paths (extended abstract)
- Fixed points of parking functions
- Combinatorics of the zeta map on rational Dyck paths
- On the sweep map for \(\vec{k}\)-Dyck paths
- Inverting the rational sweep map
- Rational Shi tableaux and the skew length statistic
- Irreducible components of minuscule affine Deligne-Lusztig varieties
- Sweeping up zeta
- From Anderson to zeta
- An area-depth symmetric \(q, t\)-Catalan polynomial
- Sweeping up zeta
- On parking functions and the zeta map in types B, C and D
- Hopf dreams and diagonal harmonics
- Recursions for rational \(q,t\)-Catalan numbers
- Recursions for rational \(q,t\)-Catalan numbers
- On the sweep map for fuss rational Dyck paths
- Dihedral sieving on cluster complexes
- Rational Dyck paths in the non relatively prime case
- Advances in the theory of cores and simultaneous core partitions
- Toric braids and (m,n)-parking functions
This page was built for publication: Sweep maps: a continuous family of sorting algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q499290)
