Multitree

<h2 id="equivalence-between-dag-and-poset-definitions">Equivalence between DAG and poset definitions</h2>
<p>In a directed acyclic graph, if there is at most one directed path between any two vertices, or equivalently if the subgraph reachable from any vertex induces an undirected tree, then its <a href="/facts/Reachability/D8cQpSFQ">reachability</a> relation is a diamond-free partial order. Conversely, in a diamond-free partial order, the <a href="/facts/Transitive_reduction/UemedaAE">transitive reduction</a> identifies a directed acyclic graph in which the subgraph reachable from any vertex induces an undirected tree.
</p>
<h2 id="diamond-free-families">Diamond-free families</h2>
<p>A diamond-free <a href="/facts/Family_of_sets/WbYof7lP">family of sets</a> is a family <i>F</i> of sets whose inclusion ordering forms a diamond-free poset. If <i>D</i>(<i>n</i>) denotes the largest possible diamond-free family of subsets of an <i>n</i>-element set, then it is known that
</p>

2
        ≤
        
          lim
          
            n
            →
            ∞
          
        
        D
        (
        n
        )
        
          
            /
          
        
        
          
            
              (
            
            
              n
              
                ⌊
                n
                
                  /
                
                2
                ⌋
              
            
            
              )
            
          
        
        ≤
        2
        
          
            3
            11
          
        
      
    
    {\displaystyle 2\leq \lim _{n\to \infty }D(n){\Big /}{\binom {n}{\lfloor n/2\rfloor }}\leq 2{\frac {3}{11}}}
  
,
<p>and it is conjectured that the limit is 2.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
<h2 id="related-structures">Related structures</h2>
<p>A <a href="/facts/Polytree/pcJa4qeS">polytree</a>, a directed acyclic graph formed by <a href="/facts/Orientation_(graph_theory)/GV2KdNtn">orienting</a> the edges of an undirected tree, is a special case of a multitree.
</p><p>The subgraph reachable from any vertex in a multitree is an <a href="/facts/Arborescence_(graph_theory)/qFKvoaLJ">arborescence</a> rooted in the vertex, that is a polytree in which all edges are oriented away from the root.
</p><p>The word "multitree" has also been used to refer to a <a href="/facts/Series%25E2%2580%2593parallel_partial_order/X8VP9aRR">series–parallel partial order</a>,<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> or to other structures formed by combining multiple trees.
</p>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Griggs, Jerrold R.; Li, Wei-Tian; Lu, Linyuan (2010), Diamond-free families, arXiv:1010.5311, Bibcode:2010arXiv1010.5311G. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Allender, Eric; Lange, Klaus-Jörn (1996), "StUSPACE(log n) ⊆ DSPACE(log2 n/log log n)", Algorithms and Computation, 7th International Symposium, ISAAC '96, Osaka, Japan, December 16–18, 1996, Proceedings, Lecture Notes in Computer Science, vol. 1178, Springer-Verlag, pp. 193–202, doi:10.1007/BFb0009495. <a href="/wiki/Eric_Allender" target="_blank">/wiki/Eric_Allender</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>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, S2CID 18710118. <a href="/wiki/George_Furnas" target="_blank">/wiki/George_Furnas</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>McGuffin, Michael J.; Balakrishnan, Ravin (2005), "Interactive visualization of genealogical graphs", IEEE Symposium on Information Visualization, Los Alamitos, California, US: IEEE Computer Society, p. 3, doi:10.1109/INFOVIS.2005.22, S2CID 15449409. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Griggs, Jerrold R.; Li, Wei-Tian; Lu, Linyuan (2010), Diamond-free families, arXiv:1010.5311, Bibcode:2010arXiv1010.5311G. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>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, MR 0491356. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
</ol>

Multitree open-in-new

Multitree