Multitree

In combinatorics and order theory, a multitree may describe either of two equivalent structures: a directed acyclic graph (DAG) in which there is at most one directed path between any two vertices, or equivalently in which the subgraph reachable from any vertex induces an undirected tree, or a partially ordered set (poset) that does not have four items a, b, c, and d forming a diamond suborder with a ≤ b ≤ d and a ≤ c ≤ d but with b and c incomparable to each other (also called a diamond-free poset[1]).

Conversely, in a diamond-free partial order, the transitive reduction identifies a directed acyclic graph in which the subgraph reachable from any vertex induces an undirected tree.

If D(n) denotes the largest possible diamond-free family of subsets of an n-element set, then it is known that and it is conjectured that the limit is 2.

[1] A polytree, a directed acyclic graph formed by orienting the edges of an undirected tree, is a special case of a multitree.

The word "multitree" has also been used to refer to a series–parallel partial order,[5] or to other structures formed by combining multiple trees.