Multitree

In combinatorics and order-theoretic mathematics, a multitree may describe either of two equivalent structures: a directed acyclic graph in which the set of nodes reachable from any node form a tree, or a partially ordered set (also called a diamond-free poset^[1]) 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.

Equivalence between DAG and poset definitions

If G is a directed acyclic graph in which the nodes reachable from each vertex form a tree (or equivalently, if G is a directed graph in which there is at most one directed path between any two nodes, in either direction) then the reachability relation in G forms a diamond-free partial order. Conversely, if P is a diamond-free partial order, its transitive reduction forms a DAG in which the successors of any node form a tree.

Diamond-free families

A diamond-free family of sets is a family F of sets whose inclusion ordering forms a diamond-free poset. If D(n) denotes the largest possible diamond-free family of subsets of an n-element set, then it is known that

$2\le \lim_{n\to\infty} D(n) \Big/ \binom{n}{\lfloor n/2\rfloor}\le 2\frac{3}{11}$

and it is conjectured that the limit is 2.^[1]

Applications

Multitrees may be used to represent multiple overlapping taxonomies over the same ground set.^[2] If a family tree may contain multiple marriages from one family to another, but does not contain marriages between any two blood relatives, then it forms a multitree.^[3] In the context of computational complexity theory, multitrees have also been called strongly unambiguous graphs or mangroves; they can be used to model nondeterministic algorithms in which there is at most one computational path connecting any two states.^[4]

Related structures

A polytree, a directed acyclic graph formed by assigning an orientation to each edge of an undirected tree, may be viewed as 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.

References

1. ^ ^{a b} Griggs, Jerrold R.; Li, Wei-Tian; Lu, Linyuan (2010), Diamond-free families, arXiv:1010.5311 .
2. ^ Furnas, George W.; Zacks, Jeff (1994), "Multitrees: enriching and reusing hierarchical structure", Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94), pp. 330–336, doi:10.1145/191666.191778 .
3. ^ McGuffin, Michael J.; Balakrishnan, Ravin (2005), "Interactive visualization of genealogical graphs", IEEE Symposium on Information Visualization, Los Alamitos, CA, USA: IEEE Computer Society, pp. 3–3, doi:10.1109/INFOVIS.2005.22 .
4. ^ Allender, Eric; Lange, Klaus-Jörn (1996), "StUSPACE(log n) ⊆ DSPACE(log² n/log log n)", Algorithms and Computation, 7th International Symposium, ISAAC '96, Osaka, Japan, December 16–18, 1996, Proceedings, Lecture Notes in Computer Science, 1178, Springer-Verlag, pp. 193–202, doi:10.1007/BFb0009495 .
5. ^ Jung, H. A. (1978), "On a class of posets and the corresponding comparability graphs", Journal of Combinatorial Theory, Series B 24 (2): 125–133, doi:10.1016/0095-8956(78)90013-8, MR0491356 .