1
$\begingroup$

Define the notion of a "foo digraph" recursively as follows.

  • If we take any finite number of directed path graphs each of which has at least $2$ vertexes, and glue them at the start and end vertexes, the result is a foo digraph.

  • If we take any foo digraph and replace an edge in that digraph with a foo digraph pointing `in the correct direction,' the result is a foo digraph.

  • Nothing else is a foo digraph.

For example:

enter image description here

is a foo digraph, where the arrows implicitly point down.

So basically, we're talking about directed acyclic graphs that equal their own transitive reductions, subject to some constraints saying that certain subgraphs like

enter image description here

can't appear, and some completeness conditions saying that there's a start vertex $\top$, and end vertex $\bot$, and that each vertex $v$ must correspond to another vertex $v'$ such that the out-degree of $v$ equals the in degree of $v'$, and the set of paths from $\top$ to $\bot$ that pass through $v$ equals the set of paths from $\top$ to $\bot$ that pass through $v'$.

The above may not be a complete characterization.

Question. Is there a name for what I'm calling foo digraphs, and are any decent graph-theoretic characterizations known?

$\endgroup$
  • 3
    $\begingroup$ This is series-parallel graph (which is undirected, but can be uniquely made directed). $\endgroup$ – Yuzhou Gu Sep 28 '17 at 11:22
  • $\begingroup$ 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. $\endgroup$ – Peter Heinig Sep 28 '17 at 17:59
  • $\begingroup$ 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. $\endgroup$ – Peter Heinig Sep 28 '17 at 18:10
  • $\begingroup$ @PeterHeinig: triangles are allowed, I think. $\endgroup$ – Martin Rubey Sep 28 '17 at 20:48
  • $\begingroup$ @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. $\endgroup$ – Peter Heinig Sep 29 '17 at 5:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.