Let $P = (V,\leq_P)$ be a poset, and for each $x \in V$ let $x^P = \{ y \in V : x \leq_P y \}$. A well-known property of certain posets (forests, Young diagrams) is the existence of a simple hook length formula counting their linear extensions - while the problem is $\# P$-hard in general. To make this notion precise, we say that $P$ has a hook length formula if there exists a function $h : V \rightarrow \mathbb{N}$ such that for every $x \in V$, the number of extensions of $P | x^P$ is equal to:

L(x) = $\frac{|x^P|!}{\prod_{y \geq_P x} h(y)}$.

It can be seen that this property is preserved by some natural operations: parallel composition, adjonction of a minimal or maximal element. This immediately implies the Knuth hook formula for forests, although it has a number of different proofs (including some of algorithmic nature).

I'd like to know if there are examples of other operations preserving/breaking the existence of a hook length formula, in particular is it possible to define a gluing operation extending the above adjonction operation?


1 Answer 1


Consider two posets $P,Q$ and an element $x \in V(P)$. Let $Pe(x)$ denote the immediate predecessors of $x$ and let $Su(x)$ denote the immediate successors of $x$ in $P$. Let $Min_Q,Max_Q$ denote the minimal, resp. maximal, elements of $Q$. Fix two mappings $Conn_1 : Pe(x) \rightarrow Min_Q$ and $Conn_2 : Su(x) \rightarrow Max_Q$. It is then possible to define a poset $R$ by starting with $(P - x) \uplus Q$ and by adding an arc $(w,Conn_1(w))$ for each $w \in Pe(x)$, and an arc $(w,Conn_2(w))$ for each $w \in Su(x)$.

This operation has a simple meaning for trees: given a tree $T$, you pick a node $u$, and you substitute it by a tree $T'$ by attaching the leaves of $T'$ to the children of $u$ in an injective manner. This means that the trees are closed under this operation of substitution, and thus we could expect that it preserves the property you're interested in. I admit though that I have no idea of what I'm doing with this defn, this might be a joke so please check on your side :)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.