<p>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)$.</p>

<p>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 :)</p>

CC BY-SA 3.0
2014-04-03T12:20:29.933Z
2014-04-03T12:20:29.933Z
NisaiVloot
<p>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 <em>hook length formula</em> 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:</p>

<blockquote>
  <p>L(x) = $\frac{|x^P|!}{\prod_{y \geq_P x} h(y)}$.</p>
</blockquote>

<p>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).</p>

<p>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?</p>

<order-theory>
Hook length formuli and their invariance properties?
NisaiVloot
# Hook length formuli and their invariance properties?

(Asked by: username_0 on 2014-04-01)

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?

**Tags:** order-theory


---

## 1 answers

### Answer by username_0 on 2014-04-03. Score: 0 | Accepted answer

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 :)


---

