A generalization of RSK to $d$-complete posets

Abstract

The hook length formula for $d$-complete posets expresses the number of linear extensions of a $d$-complete poset $P$ in terms of hooks of $P$. It generalizes the usual hook length formula for standard Young tableaux, as well as hook length formulas for shifted Young tableaux and trees. We give a new proof of the hook length formula for $d$-complete posets which is elementary and purely combinatorial. Our approach is to define a generalization of the Robinson-Schensted-Knuth bijection for $d$-complete posets, which may be of independent interest.

arXiv comment24 pages