Asymptotic and exact results on the complexity of the Novelli-Pak-Stoyanovskii algorithm

MaRDI QIDQ2628258zbMATH OpenFDO

Authors Carsten Schneider, Robin Sulzgruber

Publication date 13 June 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.07597, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p28

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

average case and worst case complexityhook-length formulaNovelli-Pak-Stoyanovskii algorithmstandard Young tableausymbolic summation

Mathematics Subject Classification ID

Combinatorial aspects of representation theory (05E10) Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.) (33F10) Symbolic computation and algebraic computation (68W30)

Abstract: The Novelli-Pak-Stoyanovskii algorithm is a sorting algorithm for Young tableaux of a fixed shape that was originally devised to give a bijective proof of the hook-length formula. We obtain new asymptotic results on the average case and worst case complexity of this algorithm as the underlying shape tends to a fixed limit curve. Furthermore, using the summation package Sigma we prove an exact formula for the average case complexity when the underlying shape consists of only two rows. We thereby answer questions posed by Krattenthaler and M"uller.

Review text

Summary: The Novelli-Pak-Stoyanovskii algorithm is a sorting algorithm for Young tableaux of a fixed shape that was originally devised to give a bijective proof of the hook-length formula. We obtain new asymptotic results on the average case and worst case complexity of this algorithm as the underlying shape tends to a fixed limit curve. Furthermore, using the summation package Sigma we prove an exact formula for the average case complexity when the underlying shape consists of only two rows. We thereby answer questions posed by Krattenthaler and Müller.

Recommendations

• A complexity theorem for the Novelli-Pak-Stoyanovskii algorithm
• Symmetry properties of the Novelli-Pak-Stoyanovskii algorithm
• scientific article; zbMATH DE number 1375571
• Another involution principle-free bijective proof of Stanley's hook-content formula
• A q-analog of the hook walk algorithm for random Young tableaux

Cites work

• A \textit{Mathematica} version of Zeilberger's algorithm for proving binomial coefficient identities
• A complexity theorem for the Novelli-Pak-Stoyanovskii algorithm
• A difference ring theory for symbolic summation
• A variational problem for random Young tableaux
• Another involution principle-free bijective proof of Stanley's hook-content formula
• Calculating three loop ladder and V-topologies for massive operator matrix elements by computer algebra
• scientific article; zbMATH DE number 1601795 (Why is no real title available?)
• scientific article; zbMATH DE number 1375571 (Why is no real title available?)
• scientific article; zbMATH DE number 1263410 (Why is no real title available?)
• scientific article; zbMATH DE number 872231 (Why is no real title available?)
• Simplifying multiple sums in difference fields
• Summation in Finite Terms
• Summation theory. II: Characterizations of \(R {\Pi}{\Sigma}^{\ast}\)-extensions and algorithmic aspects
• Symbolic summation assists combinatorics
• The Hook Graphs of the Symmetric Group
• XXVI.—The Monomial Expansion of Determinantal Symmetric Functions

Cited in

(7)

• On parking functions and the zeta map in types B, C and D
• Symmetry properties of the Novelli-Pak-Stoyanovskii algorithm
• A complexity theorem for the Novelli-Pak-Stoyanovskii algorithm
• Term algebras, canonical representations and difference ring theory for symbolic summation
• Some natural extensions of the parking space
• Bijecting hidden symmetries for skew staircase shapes
• On a class of strongly asymmetric PKA algorithms

Describes a project that uses

Uses Software

• EvaluateMultiSums
• GeneratingFunctions
• SIGMA

This page was built for publication: Asymptotic and exact results on the complexity 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 Q2628258)