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 the first purely combinatorial proof of the hook length formula for d-complete posets. Our approach is to define a generalization of the Robinson-Schensted-Knuth bijection for d-complete posets, which may be of independent interest.