Forest and Tree Posets

Forest Posets and Tree Posets

1. Two Structures on Vertices and Edges

Let $(V,\leq_V)$ be a finite tree poset with a unique minimal element $r$. Thus, for every $v\in V$, the principal down-set

$$\downarrow v=\{u\in V:u\leq_V v\}$$

is a chain. The Hasse diagram of $(V,\leq_V)$ is therefore a rooted tree with root $r$.

The same rooted tree also carries a natural structure on its edge set. Every non-root vertex has a unique predecessor. If $v\neq r$, let $p(v)$ denote the unique lower cover of $v$ and associate with $v$ the edge

$$e_v=\{p(v),v\}.$$

This defines

$$\mathcal E_r:V\setminus\{r\}\longrightarrow E,\qquad \mathcal E_r(v)=e_v.$$

Every edge joins a vertex to its unique predecessor, so $\mathcal E_r$ is a bijection. The root is the only vertex that does not correspond to an edge.

This suggests that the rooted structure on $V$ should have a corresponding structure directly on $E$. However, removing the root changes the type of the structure. A single rooted tree on $V$ becomes several rooted branches on $E$.

2. From a Tree Poset to a Forest Poset

Use $\mathcal E_r$ to transfer the order from $V\setminus\{r\}$ to $E$. Define

$$e_u\leq_E e_v\quad\Longleftrightarrow\quad u\leq_V v.$$

For every $e_v\in E$,

$$\downarrow e_v=\mathcal E_r\bigl(\downarrow v\setminus\{r\}\bigr).$$

Since $\downarrow v$ is a chain, $\downarrow e_v$ is also a chain. Hence $(E,\leq_E)$ is a forest poset.

The minimal elements of $(E,\leq_E)$ are precisely the edges incident with $r$. Each such edge begins one branch of the original rooted tree. Consequently, the Hasse diagram of $(E,\leq_E)$ is a forest of rooted trees rather than a single rooted tree.

Geometrically, this operation removes the common root $r$ from the vertex tree. The branches separate, and each edge incident with $r$ becomes the root of one component of the edge forest. The missing root is not represented by an additional edge. It is represented by the fact that the different components originally shared a common vertex.

3. From a Forest Poset Back to a Tree Poset

The construction can be reversed without introducing a formal edge. Let $(E,\leq_E)$ be a finite forest poset, meaning that every principal down-set is a chain.

Introduce one new element $r$ and set

$$V=E\sqcup\{r\}.$$

For each $e\in E$, if $e$ is minimal, connect it directly to $r$. If $e$ is not minimal, the chain property guarantees that $e$ has a unique lower cover, and we connect $e$ to this lower cover.

Every component of the forest is therefore attached to the same new vertex $r$. The resulting graph is connected and acyclic, hence it is a tree rooted at $r$. Its ancestor relation defines a tree poset $(V,\leq_V)$.

The geometric interpretation is the reverse of the previous construction. A forest poset consists of several rooted branches. Reconstructing the vertex tree amounts to merging the roots of these branches through one common vertex $r$.

4. The Tree-Forest Correspondence

The two constructions are mutually inverse. Starting from a finite tree poset $(V,\leq_V)$ with root $r$, construct $(E,\leq_E)$ through

$$\mathcal E_r(v)=\{p(v),v\},\qquad v\neq r.$$

Reconstructing from $(E,\leq_E)$ adds one common root and reconnects every minimal edge to it. The original rooted tree is recovered up to the natural identification

$$v\longleftrightarrow e_v,\qquad v\neq r.$$

Conversely, starting with a finite forest poset $(E,\leq_E)$, adding the common root $r$ gives a tree poset. Applying $\mathcal E_r$ then sends each non-root vertex back to the edge determined by its unique predecessor, recovering the original forest poset.

Thus there is a one-to-one correspondence

$$\{\text{finite tree posets with a distinguished root}\}\longleftrightarrow\{\text{finite forest posets}\},$$

realized explicitly by

$$\mathcal E_r:V\setminus\{r\}\longrightarrow E.$$

The two sides are not the same object written in different notation. A tree poset is carried by vertices and contains its root as an element. A forest poset is carried by edges and contains no element corresponding to that root. The root appears instead as the common gluing point of the components when the forest is reconstructed as a tree.

The structural insight can therefore be summarized as

$$\text{tree poset}=\text{forest poset}+\text{one common root}.$$

In particular, the relation $|V|=|E|+1$ is not a defect that needs to be repaired by introducing a formal edge. It reflects the geometry of the correspondence itself. Removing the root separates a rooted tree into edge branches, while adding one common root merges those branches back into a rooted tree.