Diamond lemma for edge-colored directed graphs Suppose we have a directed graph with colored edges such that (1) every vertex has at most one outgoing edge of each color, (2) for any path of length two, say from $u$ to $v$ to $w$, there exists a vertex $v'$ and a directed path from $u$ to $v'$ to $w$ such that edge $(u,v')$ has the same color as edge $(v,w)$ and edge $(v',w)$ has the same color as edge $(u,v)$, and (3) for all $v$, if we have distinct edges $(v,w)$ and $(v,w')$, there exists $x$ and edges $(w,x)$ and $(w',x)$ with the same color as $(v,w')$ and $(v,w)$ respectively.. Then a standard argument (the "Jordan-Holder argument") shows that, for any starting vertex $s$, EITHER there is no terminating path from $s$ (where a terminating path is one whose final vertex $t$ has no outgoing edges) OR every maximal path from $s$ terminates at a path-independent vertex $t$ and moreover the number of times each color gets used is path-independent.
Can anyone provide a citation for this lemma or something like it? (It occurs in a more specialized form in the theory of abelian sandpiles, and again in the theory of rewrite systems, and again in group theory, but it's really just a general-purpose graph-theory lemma.)
 A: Here's a proof of a more general result that Alex Postnikov presented recently in class. (Actually he did not use colors as you do but that can be incorporated into the proof.) He called the result the "Roman Lemma" because a) it may have been known to the ancient Romans and b) it is based on the principle that all roads lead to Rome. :) (There was also some discussion about its relation to the Roman Catholic Church which I will omit here.)
Recall that a sink of a directed graph is a vertex of outdegree zero.
Lemma: Let $G$ be an edge-colored directed graph, not necessarily finite, without loops but possibly with multiple edges, whose underlying undirected graph is connected. Suppose that whenever $(v,w)$ and $(v,w')$ are edges of $G$ (even with $w = w'$) there is some $k\geq 0$ and two paths $(v,w = w_0), (w_0,w_1),\ldots, (w_{k-1},w_{k} = u)$ and $(v,w' = w'_0), (w'_0,w'_1),\ldots, (w'_{k-1},w'_{k} = u)$ that bring $w$ and $w'$ back together in the same number of steps and whose multisets of edge colors are the same. Then either:
(1) $G$ has no sinks or (2) $G$ has a unique sink $q$, and starting from any fixed $v \in G$, every path from $v$ eventually leads to $q$, in the same number of steps, and moreover with the same multiset of edge colors.
(Note that (2) means that, ignoring edge colors, $G$ is the Hasse diagram of a graded poset with a unique maximal element.)
Pf: Suppose (1) does not hold. So $G$ has some sink; choose a sink $q$. For $i \geq 0$, let $L_i$ be the set of all vertices in $G$ whose shortest path to $q$ is of length $i$.
Subclaim 1: The vertices in $L_i$ have edges only to vertices in $L_{i-1}$. Thus the restriction to $L_0,L_1,\ldots,L_i$ is a Hasse diagram of a graded poset with unique maximal element $q$.
Pf: By induction on $i$. Clear for $i=0$. Suppose to the contrary that $v \in L_i$ has an edge to $w$ with $w \notin L_{i-1}$. By construction there is $w' \in L_{i-1}$ such that $(v,w')$ is also an edge. Then we can join up $w$ and $w'$ in the same number of steps to some $u$. But since by induction all paths from $w'$ to $q$ have length $i-1$, we get a path from $w$ to $q$ of length $i-1$, which contradicts $w \notin L_{i-1}$ (if $w$ is not in any $L_j$ for any $j \leq i-1$ this is clearly a contradiction; if $w$ is in $L_j$ for some $j < i-1$ then this yields a path from $v$ to $q$ via $w$ having length $j+1<i$, which contradicts $v \in L_i$).
Subclaim 2: $\bigsqcup_{i=0}^{\infty} L_i = G$.
Pf: Let $v$ be a vertex in $G$. We want to prove that $v$ has a directed path to $q$. By the assumption that the underlying undirected graph of $G$ is connected, there is an undirected path from $v$ to $q$. We prove that a directed path from $v$ to $q$ exists by induction on the length of the shortest undirected path from $v$ to $q$. It is clear if this length is zero. So let $v=v_0,v_1,v_2,\ldots,v_k=q$ be an undirected path from $v$ to $q$. If the first step is a directed edge $(v_0,v_1)$ in the right direction, then clearly we are done by induction. However, if the first step is a directed edge $(v_1,v_0)$ in the ``wrong'' direction, still we have $v_1 \in L_i$ for some $i$ by induction, and thus $v_0 \in L_{i-1}$ by Subclaim 1. So we are done.
We have now proved everything except the stuff about edge colors.
Subclaim 3 (colors): All paths from a fixed $v \in L_i$ to $q$ have the same multiset of edge colors.
Pf: Again induction on $i$. Again clear for $i=0$. Let $v \in L_i$. Suppose we have two paths $(v,w = w_0), (w_0,w_1),\ldots, (w_{i-1},w_{i} = q)$ and $(v,u = u_0), (u_0,u_1),\ldots, (u_{i-1},u_{i} = q)$. By assumption we can find two other paths $(v,w = w'_0), (w'_0,w'_1),\ldots, (w'_{k-1},w'_{k} = t)$ and  $(v,u = u'_0), (u'_0,u'_1),\ldots, (u'_{k-1},u'_{k} = t)$ with the same multisets of colors. Continue these paths from $t$ to $q$, maintaining the same multisets of colors: $(v,w'_0), (w'_0,w'_1),\ldots, (w'_{i-1},w'_{i} = q)$ and  $(v,u'_0), (u'_0,u'_1),\ldots, (u'_{i-1},u'_{i} = q)$. By induction $(w'_0,w'_1),\ldots, (w'_{i-1},w'_{i})$ has the same multiset of colors as $(w_0,w_1),\ldots, (w_{i-1},w_{i})$ and $(u'_0,u'_1),\ldots, (u'_{i-1},u'_{i})$ has the same multiset of colors as $(u_0,u_1),\ldots, (u_{i-1},u_{i})$. This meant that $(v,w_0), (w_0,w_1),\ldots, (w_{i-1},w_{i})$ and $(v,u_0), (u_0,u_1),\ldots, (u_{i-1},u_{i})$ have the same multiset of colors.
This completes the whole proof. $\square$
As for a reference, I do not know.
