✦ LIBER ✦

Complexes of Directed Trees

✍ Scribed by Dmitry N. Kozlov

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 153 KB
Volume: 88
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1999.2984

No coin nor oath required. For personal study only.

✦ Synopsis

To every directed graph G one can associate a complex 2(G) consisting of directed subforests. This construction, suggested to us by R. Stanley, is especially important in the case of a complete double directed graph G n , where it leads to the study of some interesting representations of the symmetric group and corresponds (via the Stanley Reisner correspondence) to an interesting quotient ring. Our main result states that 2(G n ) is shellable, in particular, Cohen Macaulay, which can be further translated to say that the Stanley Reisner ring of 2(G n ) is Cohen Macaulay. Besides that, by computing the homology groups of 2(G) for the cases when G is essentially a tree and when G is a double directed cycle, we touch upon the general question of the interaction of the combinatorial properties of a graph and the topological properties of the associated complex.

📜 SIMILAR VOLUMES

Optimal Labellings of Rooted Directed Tr

Optimal Labellings of Rooted Directed Trees

✍ Jia-yu Shao 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 200 KB

We consider an optimal labelling problem for a rooted directed tree abbreviated . as ''RDT'' which is motivated by certain scheduling problem. We obtain several necessary and sufficient conditions for the optimal labellings of a RDT and give a polynomially bounded algorithm for constructing the opti

Directed Tree-Width

✍ Thor Johnson; Neil Robertson; P.D. Seymour; Robin Thomas 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 198 KB

We generalize the concept of tree-width to directed graphs and prove that every directed graph with no ``haven'' of large order has small tree-width. Conversely, a digraph with a large haven has large tree-width. We also show that the Hamilton cycle problem and other NP-hard problems can be solved i

On the number of spanning trees in direc

On the number of spanning trees in directed circulant graphs

✍ Zbigniew Lonc; Krzysztof Parol; Jacek M. Wojciechowski 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB

Extracting Species Trees From Complex Ge

Extracting Species Trees From Complex Gene Trees: Reconciled Trees And Vertebrate Phylogeny

✍ Roderic D.M. Page 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 427 KB

Paralogy is a pervasive problem in trying to use nuclear gene sequences to infer species phylogenies. One strategy for dealing with this problem is to infer species phylogenies from gene trees using reconciled trees, rather than directly from the sequences themselves. In this approach, the optimal s

Decision Tree Complexity and Betti Numbe

Decision Tree Complexity and Betti Numbers

✍ Andrew Chi-Chih Yao 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 381 KB

We show that any algebraic computation tree or any fixed-degree algebraic tree for solving the membership question of a compact set S R n must have height greater than 0(log(; i (S)))&cn for each i, where ; i (S) is the ith Betti number. This generalizes a well-known result by Ben-Or who proved this

The Complexity of Scheduling Trees with

The Complexity of Scheduling Trees with Communication Delays

✍ Jan Karel Lenstra; Marinus Veldhorst; Bart Veltman 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 190 KB

We consider the problem of finding a minimum-length schedule on m machines for a set of n unit-length tasks with a forest of intrees as precedence relation, and with unit interprocessor communication delays. First, we prove that this problem is NP-complete; second, we derive a linear time algorithm