Timeline for Is there a name for these especially simple directed acyclic graphs, and are any decent characterizations known?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 29, 2017 at 5:46 | comment | added | Peter Heinig | One should add that while Yuzhou Gu seems to have exactly identified the class defined by Goblin, this thread is still lacking a precise reference to one of the several definitions of $\mathsf{SeriesParallelGraphs}$ which would make it obvious that goblin's graphs are precisely (orientations of) series-parallel graphs. I can imagine someone working on something, under time pressure, stumbling upon this thread, finding goblin's graphs exactly what they need, seeing 'series-parallel', but noticing that the correspondence with the Wikipedia page is not evident, and missing something verifiable. | |
| Sep 29, 2017 at 5:32 | comment | added | Peter Heinig | @MartinRubey: you are right in saying that triangles are allowed by goblin, more precisely, goblin allows one to construct a transitive tournaments on three vertices, and $\text{ therefore Hasse diagrams are irrelevant here}$ (please note I only said 'probably'). How to get a transitive triangle from goblin's axioms: start with two copies of a directed path, glued at their endvertices (= 'oriented dipole' ), then apple goblin's second axiom to replace one of the constituent 2-vertex paths by a 3-vertex directed path. | |
| Sep 28, 2017 at 20:48 | comment | added | Martin Rubey | @PeterHeinig: triangles are allowed, I think. | |
| Sep 28, 2017 at 18:10 | comment | added | Peter Heinig | One can probably characterize this as follows: 'a digraph $D$ is a foo-digraph if and only if it is (the downwards orientation of) a *Hasse diagram of a finite poset with both a greatest and a least element and property $P$', where I am unsure at the moment what the right $P$ is. | |
| Sep 28, 2017 at 17:59 | comment | added | Peter Heinig | Worth pointing out: if $D$ is a foo-digraph, then the free category generated by $G$ is a confluent category. I have not looked into the question if and how the converse holds. | |
| S Sep 28, 2017 at 17:52 | history | suggested | David G. Stork | CC BY-SA 3.0 |
added graphs with arrows (since they are "directed")
|
| Sep 28, 2017 at 17:24 | review | Suggested edits | |||
| S Sep 28, 2017 at 17:52 | |||||
| Sep 28, 2017 at 11:22 | comment | added | Yuzhou Gu | This is series-parallel graph (which is undirected, but can be uniquely made directed). | |
| Sep 28, 2017 at 11:13 | history | asked | goblin GONE | CC BY-SA 3.0 |