Confluence and the unique attracting region

Confluence on directed graphs: from local conditions to a unique attracting region

1. Local and global confluence

Let $G=(V,E)$ be a directed graph, where $V$ is a set of vertices and $E\subseteq V\times V$ is a set of directed edges. We write $x\to y$ when $(x,y)\in E$. At this stage, the graph need not be finite or connected, and loops are allowed.

We write $x\leadsto y$ when there is a finite directed walk from $x$ to $y$: there exist an integer $n\geq 0$ and vertices $x_0,\ldots,x_n$ such that $x_0=x$, $x_n=y$, and $x_i\to x_{i+1}$ for every $0\leq i<n$. Vertices may repeat, and walks of length $0$ are allowed. In particular, $x\leadsto x$ holds without requiring a loop $x\to x$. Reachability is transitive: if $x\leadsto y$ and $y\leadsto z$, then $x\leadsto z$.

Definition (Local confluence). The graph $G$ is locally confluent if, for every $x,a,b\in V$,

$$x\to a,\qquad x\to b \quad\Longrightarrow\quad \exists c\in V:\ a\leadsto c,\quad b\leadsto c.$$

Thus, whenever two directed edges leave the same vertex, their endpoints can reach a common vertex.

Definition (Global confluence). The graph $G$ is globally confluent if, for every $x,u,v\in V$,

$$x\leadsto u,\qquad x\leadsto v \quad\Longrightarrow\quad \exists w\in V:\ u\leadsto w,\quad v\leadsto w.$$

The difference is the length of the initial branches: local confluence considers two single edges, whereas global confluence considers two arbitrary finite directed walks. The walks used to join the branches may have any finite length in both definitions.

Global confluence immediately implies local confluence. The question is whether a local condition can also guarantee global confluence.

2. Termination and the absence of directed cycles

Definition (Termination). The graph $G$ is terminating if there is no infinite sequence of vertices $(x_n)_{n\geq 0}$ satisfying

$$x_n\to x_{n+1}\qquad\text{for every }n\geq 0.$$

The vertices in this sequence are allowed to repeat. For example, a loop $v\to v$ produces the infinite sequence $v\to v\to v\to\cdots$. More generally, any directed cycle can be traversed repeatedly. Therefore, termination excludes all directed cycles, including loops.

Proposition. A finite directed graph is terminating if and only if it has no directed cycle.

Proof. A directed cycle produces an infinite sequence of directed edges by repeated traversal, so a terminating graph cannot contain one. Conversely, an infinite sequence in a finite graph must repeat a vertex. The segment between two occurrences gives a nonempty closed directed walk, which contains a directed cycle. Thus, a finite graph without directed cycles is terminating. $\square$

For infinite graphs, the absence of directed cycles does not imply termination. For example, the graph with vertices $v_0,v_1,v_2,\ldots$ and edges $v_n\to v_{n+1}$ has no directed cycle but admits the infinite sequence

$$v_0\to v_1\to v_2\to\cdots.$$

Definition (Terminal vertex). A vertex $s\in V$ is terminal if it has no outgoing edge:

$$\nexists y\in V:\ s\to y.$$

In a terminating graph, every vertex can reach a terminal vertex. Indeed, starting from any vertex, continue along an outgoing edge whenever one is available. Termination forces this process to stop at a terminal vertex.

3. Newman’s lemma

Theorem (Newman’s lemma, [1]). Every terminating, locally confluent directed graph is globally confluent.

Proof. We first show that every vertex can reach exactly one terminal vertex, and then deduce global confluence.

Step 1. Every vertex can reach at least one terminal vertex.

This follows from termination, as explained in Section 2.

Step 2. Every vertex can reach at most one terminal vertex.

Suppose otherwise, and let

$$B=\{x\in V:\ x\text{ can reach two distinct terminal vertices}\}.$$

Then $B\neq\varnothing$. Termination guarantees a vertex $x\in B$ with no outgoing edge to another vertex of $B$. Indeed, if every vertex in $B$ had an outgoing edge to a vertex in $B$, repeatedly choosing such an edge would give an infinite sequence. Hence we can choose $x$ satisfying

$$x\in B,\qquad x\to y\ \Longrightarrow\ y\notin B.$$

Choose distinct terminal vertices $p,q$ that are reachable from $x$. Since $x$ is not terminal, both walks have positive length. Taking their first edges gives

$$x\to a\leadsto p,\qquad x\to b\leadsto q.$$

By the choice of $x$, neither $a$ nor $b$ belongs to $B$. Together with Step 1, this means that $a$ can reach exactly one terminal vertex, namely $p$, and $b$ can reach exactly one terminal vertex, namely $q$.

Local confluence applied to $x\to a$ and $x\to b$ gives a vertex $c$ such that

$$a\leadsto c,\qquad b\leadsto c.$$

By Step 1, $c$ can reach a terminal vertex $r$. Consequently,

$$a\leadsto c\leadsto r,\qquad b\leadsto c\leadsto r.$$

Uniqueness of the reachable terminal vertex at $a$ gives $p=r$, and uniqueness at $b$ gives $q=r$. Thus $p=q$, contradicting their choice. Therefore, $B=\varnothing$.

Step 3. The graph is globally confluent.

Suppose $x\leadsto u$ and $x\leadsto v$. By Step 1, there are terminal vertices $p,q$ such that $u\leadsto p$ and $v\leadsto q$. Both are reachable from $x$, so Step 2 gives $p=q$. Choosing $w=p=q$ yields $u\leadsto w$ and $v\leadsto w$. $\square$

Corollary (Finite version). A finite directed graph without directed cycles is globally confluent if and only if it is locally confluent.

Proof. Global confluence implies local confluence by definition. Conversely, the absence of directed cycles implies termination in a finite graph, so Newman’s lemma applies. $\square$

4. A unique attracting region

A terminal vertex describes a destination at which movement stops. To include graphs with directed cycles, we introduce a destination that may contain several vertices.

Definition (Attracting region). An attracting region is a nonempty set $A\subseteq V$ satisfying the following two properties.

(i) The subgraph induced by $A$ is strongly connected: for every $a,b\in A$, there is a finite directed walk from $a$ to $b$ whose vertices all belong to $A$.

(ii) No directed edge leaves $A$:

$$a\in A,\qquad a\to b \quad\Longrightarrow\quad b\in A.$$

Thus, vertices within an attracting region can reach one another, and any directed walk that enters the region remains inside it. Equivalently, an attracting region is a strongly connected component with no outgoing edge to another component. A strongly connected component is a maximal nonempty set of mutually reachable vertices; distinct such components are disjoint.

Definition (Basin of attraction). The basin of an attracting region $A$ is

$$\mathcal B(A)=\{x\in V:\ \exists a\in A,\ x\leadsto a\}.$$

In a terminating graph, every attracting region consists of a single terminal vertex. Indeed, two distinct vertices in a strongly connected region would give a nonempty closed directed walk, and a loop would also violate termination. Conversely, every terminal vertex forms an attracting region by itself.

Global confluence alone does not guarantee a single attracting region for the whole graph. For example, two isolated vertices form a globally confluent graph with two attracting regions. To obtain uniqueness across the graph, we require connectivity.

We say that $G$ is weakly connected, or connected after forgetting edge directions, if for every $u,v\in V$ there is a finite sequence

$$u=x_0,x_1,\ldots,x_k=v$$

such that, for each $0\leq i<k$, either $x_i\to x_{i+1}$ or $x_{i+1}\to x_i$.

Theorem (Unique attracting region). Let $G$ be a finite, nonempty, weakly connected directed graph. If $G$ is globally confluent, then it has exactly one attracting region $A$, and

$$\mathcal B(A)=V.$$

Directed cycles are allowed in this theorem.

Proof.

Step 1. Every vertex can reach at least one attracting region.

Fix a vertex $x$, and let $C_0$ be its strongly connected component. If an edge leaves $C_0$, follow it to another component $C_1$. Strong connectivity allows us to reach the initial vertex of any outgoing edge within the current component. Continue whenever an outgoing edge to another component is available.

This process cannot return to a component already visited. Otherwise, the components along the resulting cycle would be mutually reachable and would belong to a single strongly connected component. Since there are finitely many components, the process eventually reaches a component with no outgoing edge to another component. This is an attracting region reachable from $x$.

Step 2. Every vertex can reach at most one attracting region.

Suppose $x$ can reach attracting regions $A$ and $B$. Choose $a\in A$ and $b\in B$ with $x\leadsto a$ and $x\leadsto b$. Global confluence gives a vertex $c$ such that

$$a\leadsto c,\qquad b\leadsto c.$$

No directed walk starting in $A$ can leave $A$, so $c\in A$. Similarly, $c\in B$. Thus $A$ and $B$ are strongly connected components with a common vertex, and therefore $A=B$.

By Steps 1 and 2, denote by $A(x)$ the unique attracting region reachable from $x$.

Step 3. The endpoints of every edge have the same attracting region.

If $x\to y$, then $x$ can reach every vertex that $y$ can reach. In particular, $x$ can reach $A(y)$. Uniqueness from Step 2 gives

$$A(x)=A(y).$$

Thus, the endpoints of an edge have the same attracting region regardless of the direction of that edge.

Step 4. All vertices have the same attracting region.

For arbitrary $u,v\in V$, weak connectivity gives a finite sequence $u=x_0,x_1,\ldots,x_k=v$ with an edge in one direction between each consecutive pair. Applying Step 3 along the sequence yields

$$A(u)=A(x_1)=\cdots=A(v).$$

Hence all vertices can reach the same attracting region $A$, so $\mathcal B(A)=V$. Any attracting region is reachable from each of its own vertices, and therefore must equal $A$. This proves uniqueness. $\square$

Corollary. Let $G$ be a finite, nonempty, weakly connected directed graph without directed cycles. If $G$ is locally confluent, then there is exactly one terminal vertex $s$, and every vertex can reach $s$:

$$\forall x\in V,\qquad x\leadsto s.$$

Proof. The absence of directed cycles gives termination. Newman’s lemma gives global confluence, and the unique attracting region theorem gives an attracting region reachable from every vertex. Termination forces this region to consist of one terminal vertex. $\square$

References

[1] Newman, M. H. A. On Theories with a Combinatorial Definition of “Equivalence”. Annals of Mathematics, Second Series, 43(2), 223–243, 1942. https://doi.org/10.2307/1968867.