https://en.formulasearchengine.com/w/api.php?action=feedcontributions&feedformat=atom&user=128.210.3.54formulasearchengine - User contributions [en]2026-09-24T15:33:52ZUser contributionsMediaWiki 1.47.0-wmf.7https://en.formulasearchengine.com/w/index.php?title=Approximate_limit&diff=25547Approximate limit2013-03-08T15:12:22Z<p>128.210.3.54: Various fixes - This still needs a lot of work, but at least it's somewhat readable now...</p>
<hr />
<div>[[File:Butterfly multitree.svg|thumb|300px|The butterfly network, a multitree used in distributed computation, showing the subtree reachable from one of its nodes]]<br />
In [[combinatorics]] and [[order theory|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 (graph theory)|tree]], or a [[partially ordered set]] that does not have four items ''a'', ''b'', ''c'', and ''d'' forming a diamond suborder with {{nowrap|''a'' ≤ ''b'' ≤ ''d''}} and {{nowrap|''a'' ≤ ''c'' ≤ ''d''}} but with ''b'' and ''c'' incomparable to each other (also called a '''diamond-free poset'''<ref name="gll">{{citation<br />
| last1 = Griggs | first1 = Jerrold R.<br />
| last2 = Li | first2 = Wei-Tian<br />
| last3 = Lu | first3 = Linyuan<br />
| title = Diamond-free families<br />
| year = 2010<br />
| arxiv = 1010.5311}}.</ref>). <br />
<br />
==Equivalence between directed acyclic graph and poset definitions==<br />
If ''G'' is a directed acyclic graph ("DAG") 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.<br />
<br />
==Diamond-free families==<br />
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<br />
:<math>2\le \lim_{n\to\infty} D(n) \Big/ \binom{n}{\lfloor n/2\rfloor}\le 2\frac{3}{11}</math><br />
and it is conjectured that the limit is 2.<ref name="gll"/><br />
<br />
==Applications==<br />
Multitrees may be used to represent multiple overlapping [[Taxonomy (general)|taxonomies]] over the same ground set.<ref>{{citation<br />
| last1 = Furnas | first1 = George W. | author1-link = George Furnas<br />
| last2 = Zacks | first2 = Jeff<br />
| contribution = Multitrees: enriching and reusing hierarchical structure<br />
| doi = 10.1145/191666.191778<br />
| pages = 330–336<br />
| title = Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94)<br />
| year = 1994}}.</ref> 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.<ref>{{citation<br />
| last1 = McGuffin | first1 = Michael J.<br />
| last2 = Balakrishnan | first2 = Ravin<br />
| contribution = Interactive visualization of genealogical graphs<br />
| doi = 10.1109/INFOVIS.2005.22<br />
| location = Los Alamitos, CA, USA<br />
| publisher = IEEE Computer Society<br />
| title = IEEE Symposium on Information Visualization<br />
| year = 2005<br />
| pages = 3–3}}.</ref> In the context of [[computational complexity theory]], multitrees have also been called '''strongly unambiguous graphs''' or '''mangroves'''; they can be used to model [[nondeterministic algorithm]]s in which there is at most one computational path connecting any two states.<ref>{{citation<br />
| last1 = Allender | first1 = Eric | author1-link = Eric Allender<br />
| last2 = Lange | first2 = Klaus-Jörn<br />
| contribution = {{nowrap|StUSPACE(log ''n'') ⊆ DSPACE(log<sup>2</sup> ''n''/log log ''n'')}}<br />
| doi = 10.1007/BFb0009495<br />
| pages = 193–202<br />
| publisher = Springer-Verlag<br />
| series = Lecture Notes in Computer Science<br />
| title = Algorithms and Computation, 7th International Symposium, ISAAC '96, Osaka, Japan, December 16–18, 1996, Proceedings<br />
| volume = 1178<br />
| year = 1996}}.</ref> <br />
<br />
==Related structures==<br />
A [[polytree]], a [[directed acyclic graph]] formed by assigning an orientation to each edge of an undirected [[tree (graph theory)|tree]], may be viewed as a special case of a multitree.<br />
<br />
The set of all nodes connected to any node ''u'' in a multitree forms an [[Arborescence_(graph_theory)|arborescence]].<br />
<br />
The word "multitree" has also been used to refer to a [[series-parallel partial order]],<ref>{{citation<br />
| last = Jung | first = H. A.<br />
| title = On a class of posets and the corresponding comparability graphs<br />
| journal = [[Journal of Combinatorial Theory]], Series B<br />
| volume = 24<br />
| year = 1978<br />
| issue = 2<br />
| pages = 125–133<br />
| id = {{MathSciNet | id = 0491356}}<br />
| doi = 10.1016/0095-8956(78)90013-8}}.</ref> or to other structures formed by combining multiple trees.<br />
<br />
==References==<br />
{{reflist}}<br />
<br />
[[Category:Order theory]]<br />
[[Category:Directed graphs]]</div>128.210.3.54