Symmetry properties of the Novelli-Pak-Stoyanovskii algorithm

zbMATH Open1393.05295MaRDI QIDQ4584101FDOQ4584101

Authors: Robin Sulzgruber 

Publication date: 29 August 2018

Abstract: The number of standard Young tableaux of a fixed shape is famously given by the hook-length formula due to Frame, Robinson and Thrall. A bijective proof of Novelli, Pak and Stoyanovskii relies on a sorting algorithm akin to jeu-de-taquin which transforms an arbitrary filling of a partition into a standard Young tableau by exchanging adjacent entries. Recently, Krattenthaler and M"uller defined the complexity of this algorithm as the average number of performed exchanges, and Neumann and the author proved it fulfils some nice symmetry properties. In this paper we recall and extend the previous results and provide new bijective proofs.

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

Recommendations

• Asymptotic and exact results on the complexity of the Novelli-Pak-Stoyanovskii algorithm
• A complexity theorem for the Novelli-Pak-Stoyanovskii algorithm
• A symmetry theorem on a modified jeu de taquin
• scientific article; zbMATH DE number 1375571
• Another involution principle-free bijective proof of Stanley's hook-content formula

zbMATH Keywords

complexityYoung tableauxhook-length formula

Mathematics Subject Classification ID

Combinatorial aspects of representation theory (05E10) Combinatorial identities, bijective combinatorics (05A19)

Cited In (9)

• A symmetry theorem on a modified jeu de taquin
• Title not available (Why is that?)
• Enumeration of Standard Young Tableaux
• Another involution principle-free bijective proof of Stanley's hook-content formula
• Experimenting with standard Young tableaux
• Hook inequalities
• On a class of strongly asymmetric PKA algorithms
• A complexity theorem for the Novelli-Pak-Stoyanovskii algorithm
• Asymptotic and exact results on the complexity of the Novelli-Pak-Stoyanovskii algorithm

This page was built for publication: Symmetry properties of the Novelli-Pak-Stoyanovskii algorithm

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