Embedding an algebraic object, such as a group, ring, or module, into a projective limit of well-behaved objects is a frequently used tactic in algebra and number theory. For example, in commutative algebra, polynomial rings are embedded in rings of formal power series. Or more generally, if R is any commutative ring and I is an ideal, then the I-adic completion of R is the projective limit of the inverse system of quotient rings R/Iⁿ, n ≥ 0. The case of R = ℤ and I = (p), where p is a prime, yields the p-adic integers. These rings are of particular importance in number theory.

This idea is also used for constructing compactifications of (discrete) graphs and directed graphs. For example, the ends of a finitely generated group are the ” boundary points ” of the so called end compactification of the Cayley (directed) graph of the group. The end compactification can be constructed as a certain completion of the (directed) graph which is a projective limit of finite (directed) graphs, and thus is a profinite (directed) graph (see Example 1.2). Similarly fundamental profinite groupoids are constructed using certain completions of fundamental groupoids (see 6.5).

There is a topological approach to producing such projective limits known as completion. The rough idea is to impose a suitable topology on the object making it into a topological group (or ring, or module, etc.) so that Cauchy sequences (or more generally, Cauchy nets) can be defined and used to construct the completion. By choosing different such topologies, various completions are formed. In the case of a residually finite group, Hartley [2] introduced the terminology of cofinite groups for the topological group structures that can be imposed such that the completion is a profinite group. Namely, a cofinite group is a topological group G whose open normal subgroups of finite indexeses form a neighborhood base for the identity. Our purpose in this paper is to investigate to what extent the technique of profinite completion can be extended to more general structures that may only have at most a partial multiplication; for instance, we consider graphs (in the sense of Serre [5]) and groupoids.

One feature that all the objects that will concern us here have in common is an underlying directed graph structure. (It may be quite simple, as in the case of a group, which we view as a directed graph whose vertex set consists of only the identity element.) Thus, we begin by exploring embeddings of directed graphs as dense sub-directed graphs of profinite directed graphs with the goal of developing a general theory that can be applied widely in many situations. Initially we note that, without some modification, the topological approach used in the classical situations to construct and distinguish various completions breaks down for directed graphs in general. The following easy example illustrates this point.

Example 1.1

Let Γ be the directed graph obtained by subdividing the real line at the integer points, so V (Γ) = ℤ, and directing each edge in the increasing direction. Incidentally, Γ is the Cayley directed graph of the additive group ℤ with respect to the generating set {1}. We view Γ as a topological directed graph with the discrete topology. (Our terminology and notation for directed graphs is fully explained in the next section.)

For each integer n ≥ 0, let [−n, n] denote the connected sub-directed graph of Γ with vertex set {0,±1, . . . ,±n}. Thus [−n, n] is a combinatorial arc of length 2n. There is a unique retraction θ_n: Γ → [−n, n]; it is the simplicial map defined on vertices by θ(i) = i for −n ≤ i ≤ n, θ(i) = n for i ≥ n, and θ(i) = −n for i ≤ −n. Also form the quotient directed graph Γ_n = [−n, n]/(−n = n) obtained by identifying the vertex −n with the vertex n, and let q_n : [−n, n] → Γ_n denote the natural quotient map. Thus Γ_n is a combinatorial circle of length 2n. Let φ_n = q_nθ_n: Γ → Γ_n denote the composite map of directed graphs.

For integers 0 ≤ m ≤ n, let θ_mn: [−n, n] → [−m,m] be the restriction of the retraction θ_m: Γ → [−m,m], and note that θ_mnθ_n = θ_m. Also note that θ_mn determines a map of directed graphs φ_mn: Γ_n → Γ_m on the quotient directed graphs, and φ_mnφ_n = φ_m holds. We have constructed two inverse systems of finite directed graphs and maps of directed graphs indexed by the directed set of non-negative integers: ([−n, n], θ_mn) and (Γ_n, φ_mn). Denote their inverse limits by Γ^1=lim← Γn and Γ^2=lim←[-n,n]. Endow each of the finite graphs [−n, n] and Γ_n with the discrete topology so that Γ̂₁ and Γ̂₂ are compact Hausdorff topological directed graphs.

Embed Γ in Γ̂₁ via the canonical map of directed graphs determined by the compatible family of maps φ_n: Γ → Γ_n. Then it is easy to see that Γ̂₁ = Γ∪ {∞} and its underlying topological space is the one-point compactification of the discrete underlying topological space of Γ. Similarly, Γ embeds in Γ̂₂ as a dense discrete sub-directed graph and Γ̂₂ = Γ∪ {−∞,∞} is a two-point compactification of Γ.

Thus Γ̂₁ and Γ̂₂ are non-isomorphic topological directed graphs, each containing Γ as a dense sub-directed topological directed graph. Thus endowing a directed graph Γ with a topological directed graph structure is not enough to uniquely determine a completion of Γ, and so something more is needed to define a suitable notion of a cofinite directed graph. Although, in the previous example, the relative topology that Γ inherits from each Γ̂_i is the same, namely the discrete topology, the uniform structures they induce on Γ are different.

A profinite directed graph, like any compact Hausdorff space, has a unique uniformity that induces its topology. We explore this uniform structure on a profinite directed graph in Section 3, and characterize it in terms of what we call cofinite entourages (Theorem 3.4). Then by analyzing the relative uniform structure induced on a sub-directed graph of a profinite directed graph, a natural notion of cofinite directed graph is discovered (Definition 4.1). As justification for our definition, in Section 5 we show that every cofinite graph Γ has a unique completion Γ̄ (Theorem 5.6), and it is a profinite directed graph (Theorem 5.10). Moreover, profinite directed graphs are precisely the compact cofinite directed graphs.

In Section 6 we conclude that the paper has some applications that we are interested in for future reference. Specifically we consider graphs (in the sense of Serre [5]) and groupoids. These objects are directed graphs with an additional structure. We require that the cofinite directed graph structures on them also respect the additional structure. In the case of a graph, it turns out that in general the completion of a cofinite graph is a profinite graph. However for a cofinite groupoid, we need to impose a mild restriction to ensure that the completion is a groupoid. This condition automatically holds for groupoids with only finitely many identities (such as a group, which has a unique identity), and thus the completion of a cofinite groupoid with a finite vertex set is a profinite groupoid (Theorem 6.15).

We conclude the introduction by the following motivational example: The end compactification of a directed graph.

Example 1.2

Let Γ be a connected, locally finite directed graph (see [6]). For each finite sub-directed graph ∑ of Γ, let R_∑ be the equivalence relation on Γ whose equivalence classes are the singleton subsets of E(∑) and the components of Γ E(∑). That is, (x, y) ∈ R_∑ if and only if x = y or x and y belong to the same component of Γ E(∑). Observe that R_∑ is compatible with the directed graph structure and has finite index (since Γ is connected). Let I be the non-empty directed set of all finite sub-directed graphs of Γ, partially ordered by inclusion. We have the following properties:

• 1. If ∑₁,∑₂ ∈ I and ∑₁ ⊆ ∑₂, then R_∑2 ⊆ R_∑1 .

• 2. For every x ∈ Γ, there exists ∑ ∈ I such that R_∑(x) = {x}.

• 3. ∩_∑∈I R_∑ = δ_Γ.

Hence the set {R_∑ | ∑ ∈ I} is a base for a (cofinite) uniformity on Γ. The completion of Γ (endowed with this cofinite structure) is given by Γ^=lim← ΓΣ and is called the end compactification of Γ. In particular, the end compactification of Γ is a profinite directed graph and Γ is a discrete open sub-directed graph of Γ̂.

2.1. Co-discrete Equivalence Relations

We do not distinguish between a binary relation and its graph. Thus, by a binary relation on a set X we mean simply a subset R ⊆ X × X. Given a binary relation R on a set X and a ∈ X, we write R[a] = {x ∈ X | (a, x) ∈ R}. More generally, for any subset A of X, we put R[A] = ∪{R[a] | a ∈ A}.

The composition of two binary relations R and S on a set X, is the binary relation SR ⊆ X ×X defined by: (x, z) ∈ SR if and only if there exists y ∈ X such that (x, y) ∈ R and (y, z) ∈ S. Note that composition is an associative operation on the set of binary relations on a set X.

The following lemma identifies certain equivalence relations on topological spaces that are useful in describing the uniform structure of profinite spaces. Recall that the index of an equivalence relation R on a set X is the cardinality of the set X/R of equivalence classes of X with respect to R.

2.2. Directed Graphs

A directed graph is a set Γ with a distinguished subset V (Γ) and two functions s, t: Γ → V (Γ) satisfying s(x) = t(x) = x for all x ∈ V (Γ). Each element of V (Γ) is called a vertex. We denote the complement of V (Γ) by E(Γ) = Γ V (Γ) and each e ∈ E(Γ) is called an edge with source s(e) and target t(e). Observe that the vertex set V (Γ) is determined by the source map s, and by the target map t: it is precisely the set of fixed points of each of these maps.

A topological directed graph is a directed graph Γ endowed with a topology such that the source and target functions s, t: Γ → V (Γ) are continuous maps onto the subspace V (Γ). We form the category of topological directed graphs by taking the class of objects to consist of all topological directed graphs and taking the morphisms to be all continuous maps of directed graphs. (That is, a morphism is both continuous and a map of directed graphs.) It is clear that a morphism f : Γ → Δ is an isomorphism of topological directed graphs (i.e., an isomorphism in the category of topological directed graphs) if and only if f is both a bijective map of directed graphs and a homeomorphism.

Every sub-directed graph of a topological directed graph will be regarded as a topological directed graph with the subspace topology. Likewise, if K is a compatible equivalence relation on a topological directed graph Γ, then the quotient directed graph Γ/K will always be endowed with the quotient topology making it a topological directed graph. Also given any family of topological directed graphs (Γ_i)_ı∈I, we make the product of the underlying topological spaces Γ = Π_i∈I Γ_i into a topological directed graph with source and target maps given by s(x_i) = (s(x_i)) and t(x_i) = (t(x_i)). Then the projection maps φ_i: Γ → Γ_i are continuous maps of directed graphs and it is clear that Γ is the product in the category of topological graphs. Likewise the inverse limit of an inverse system of topological directed graphs and continuous maps of directed graphs exists in the category of topological directed graphs and its underlying topological space is the inverse limit of the corresponding inverse system of underlying spaces. (It can also be constructed as a sub-directed graph of a product of directed graphs in the usual way.)

A profinite directed graph is a compact, Hausdorff, totally disconnected directed graph. Equivalently, a profinite directed graph is a projective limit of finite discrete directed graphs; see, for instance, [4] or the remarks following the proof of Theorem 3.4. It is easy to see that any closed sub-directed graph of a profinite directed graph is a profinite directed graph and that products and inverse limits of profinite directed graphs are profinite directed graphs. Note that the vertex set V (Γ) of a profinite directed graph Γ is closed, since it is the fixed point set of a continuous map of a Hausdorff space to itself. On the other hand, the edge set E(Γ) = ΓV (Γ) need not be closed.

Recall that every compact Hausdorff space X has a unique uniformity that induces its topology. This uniformity consists of all neighborhoods of the diagonal δ_X in X × X; see, for instance, [1, II.4.1, Theorem 1]. Therefore, as we may, we regard every compact Hausdorff space as a uniform space endowed with the unique uniformity inducing its topology. Our goal in this section is to characterize profinite directed graphs in terms of their unique uniform structures.

For this purpose, we make use of the following observation.

Lemma 3.1

Let X be a compact, Hausdorff, totally disconnected space and let W be an entourage of X. Then there exists an equivalence relation R on X such that R is open in X × X and R ⊆ W. In particular, R has finite index and is an entourage of X.

Definition 3.2.

(Cofinite entourage) Let Γ be a directed graph endowed with a uniformity. A cofinite entourage of Γ is a compatible equivalence relation of finite indexes on Γ which is also an entourage of Γ.

It should be noted that a directed graph Γ endowed with a uniformity always has at least one cofinite entourage, namely R = Γ × Γ. Here is a list of some fundamental properties of cofinite entourages that the reader can easily verify.

Lemma 3.3

Let Γ and Δ be directed graphs endowed with uniformities. Then their cofinite entourages have the following properties.

• (1) If R is a cofinite entourage of Γ and x ∈ Γ, then R[x] is a clopen neighborhood of x in Γ.

• (2) Every cofinite entourage of Γ is a clopen subset of Γ × Γ.

• (3) If R₁and R₂are cofinite entourages of Γ, then R₁ ∩ R₂is also a cofinite entourage of Γ.

• (4) If R is a compatible equivalence relation on Γ that contains a cofinite entourage of Γ, then R is itself a cofinite entourage.

• (5) If f : Γ → Δ is a uniformly continuous map of directed graphs and S is a cofinite entourage of Δ, then (f × f)⁻¹[S] is a cofinite entourage of Γ.

• (6) If ∑ is a sub-directed graph of Γ and R is a cofinite entourage of Γ, then the restriction R ∩ (∑ × ∑) is a cofinite entourage on ∑.

We are now ready to give our characterization of profinite directed graphs in terms of their uniform structures.

Theorem 3.4

Let Γ be a directed graph endowed with a compact Hausdorff topology. Then Γ is a profinite directed graph if and only if the set of cofinite entourages of Γ is a base for the uniformity on Γ.

Let Γ be a profinite directed graph and let ∑ be a sub-directed graph endowed with the induced uniformity. Then ∑ is Hausdorff and the family of all R∩(∑×∑) as R runs through all cofinite entourages of Γ, is a fundamental system of entourages of ∑. Since each R ∩ (∑ × ∑) is a cofinite entourage of the uniform sub-directed graph ∑, it follows that every uniform sub-directed graph ∑ of a profinite directed graph Γ has a fundamental system of entourages consisting of cofinite entourages of ∑. In light of this observation, we make the following definition.

Definition 4.1

(Cofinite directed graph) A cofinite directed graph is a directed graph Δ endowed with a Hausdroff uniformity that has a base consisting of cofinite entourages of Δ.

Note that by virtue of Theorem 3.4, profinite directed graphs are precisely the compact cofinite directed graphs. Also note that the definition of cofinite directed graphs does not assume that the source and target maps are uniformly continuous, or even continuous. However, we next observe that this is automatically true.

Theorem 4.2

Let Γ be a cofinite directed graph. Then the source and target maps s, t: Γ → V (Γ) are uniformly continuous maps onto the uniform subspace V (Γ). In particular, Γ is a Hausdorff topological graph and V (Γ) is a closed subset of Γ.

Proposition 4.3

Let Γ be an abstract directed graph endowed with the unique finest uniformity having a base consisting of compatible equivalence relations of finite indexes on Γ. Then Γ is a discrete cofinite directed graph.

Proposition 4.4

If Γ is an abstract directed graph and I is a non-empty filter base of compatible equivalence relations of finite indexes on Γ, then the following conditions on Γ endowed with the uniformity generated by I are equivalent:

• (1) Γ is Hausdorff, and so Γ is a cofinite directed graph;

• (3) Γ is totally disconnected;

• (2) ∩_R∈I R = δ_Γ, the diagonal in Γ × Γ.

In this section we define completions of cofinite directed graphs analogously to the way that completions of cofinite groups are defined in [2]. We show that every cofinite directed graph Γ has a completion Γ̄ (using a standard construction), and that it is unique up to a unique isomorphism extending the identity map on Γ. It turns out to be precisely the Hausdorff completion of its underlying uniform space (Corollary 5.7). Further generalizing the situation for cofinite groups [2], we observe that the completion Γ̄ is a profinite directed graph and that its cofinite entourages are precisely the closures R̄ in Γ̄ × Γ̄ of the cofinite entourages R of Γ. We begin with an analogue of [2, Theorem 2.1].

Theorem 5.1

Let Γ be a cofinite directed graph which is embedded as a dense uniform sub-directed graph of a compact Hausdorff topological directed graph Γ̄. If Δ is any compact Hausdorff topological directed graph and f : Γ → Δ is a uniformly continuous map of directed graphs, then there exists a unique continuous map of directed graphs f̄ : Γ̄ → Δ extending f.

Corollary 5.2

In the situation of the theorem, f¯(Γ¯)=f(Γ)¯.

Definition 5.3

(Completion) Let Γ be a cofinite directed graph. Then any compact Hausdorff topological directed graph Γ̄ that contains Γ as a dense uniform sub-directed graph is called a completion of Γ.

As an immediate consequence of Theorem 5.1, we have the following result on uniqueness of completions.

Corollary 5.4

If Γ̄₁and Γ̄₂are completions of a cofinite directed graph Γ, then there is an unique isomorphism of topological directed graphs ī: Γ̄₁ → Γ̄₂extending the identity map on Γ.

We turn now to the question of existence of completions. Let Γ be a cofinite directed graph and let I be any cofinal set of cofinite entourages of Γ. Note that (I,≤), where ≤ = ⊇ is the reverse of inclusion, is a directed set. Indeed ≤ is a partial order on I, and since I is cofinal, if R, S ∈ I, then there exists T ∈ I such that T ⊆ R ∩ S, and so T ≥ R and T ≥ S.

For each R ∈ I, put Γ_R = Γ/R (a finite discrete topological graph) and denote the quotient map Γ → Γ_R by x ↦ x_R. For R, S ∈ I with R ≤ S, observe that the identity map on Γ determines a map of directed graphs φ_RS: Γ_S → Γ_R given by φ_RS(x_S) = x_R; it is well defined since S ⊆ R and continuous since Γ_S is discrete. These maps have the properties:

• (i) φ_RR = id<sub>Γ_{R sub>for all R ∈ I; and}

• (ii) φ_RSφ_ST = φ_RT for all R ≤ S ≤ T in I.

Hence we have an inverse system of (finite discrete) topological directed graphs and (surjective) continuous maps of directed graphs (Γ_R, φ_RS)_R≤S∈I, indexed by the directed set I.

Let Γ^=lim← ΓR be the inverse limit of this inverse system (in the category of topological directed graphs) and denote the projection maps by φ_R : Γ̂ → Γ_R. Then Γ̂ is a topological directed graph and there is a canonical map of directed graphs i: Γ → Γ̂ given by i(x) = (x_R)_R∈I. Moreover, Γ̂ is compact and Hausdorff since its underlying space is an inverse limit of compact Hausdorff spaces. Thus, as usual, we regard Γ̂ as a uniform space with the unique uniformity compatible with its topology. It should be noted that the pre-images under the projection maps φ_R : Γ̂ → Γ_R of basis entourages of Γ_R form a base for the uniformity on Γ̂ (see, for instance, [1]). However, being finite and discrete, {δ<sub>Γ<sub>Rsub>} is a base for the uniformity on ΓR; and (φR × φR)⁻¹[δΓ_{Rsub>] = kerφR. Hence, the set of all ker φR, as R runs through I, is a base for the uniformity on Γ̂.}

With this setup, we make the following observation.

Lemma 5.5

If Γ is a cofinite directed graph, then Γ^=lim← ΓR is a compact Hausdorff topological directed graph and the canonical map i: Γ → Γ̂ is a uniform embedding whose image i(Γ) is a dense sub-directed graph of Γ̂.

Theorem 5.6

(Existence and uniqueness of completions) Every cofinite directed graph Γ has a completion, and it is unique up to an unique isomorphism of topological directed graphs extending the identity map on Γ.

Corollary 5.7

If Γ is a cofinite directed graph, then its completion Γ is equal to the Hausdorff completion of the underlying uniform space of Γ.

Lemma 5.8

If Γ is a cofinite directed graph and ∑̄ is a sub-directed graph of Γ, then ∑ is a sub-directed graph of Γ and V(Σ¯)=V(Σ)¯. In particular, V(Γ¯)=V(Γ)¯.

Lemma 5.9

Let Γ be a cofinite directed graph and let Γ̄ be its completion. If R is a cofinite entourage of Γ, then its closure R̄ in Γ̄ × Γ̄ is a cofinite entourage of Γ̄ and R̄ ∩ (Γ × Γ) = R.

Theorem 5.10

Let Γ be a cofinite directed graph. Then its completion Γ̄ is a profinite directed graph and the cofinite entourages of Γ̄ are precisely all the R̄, where R runs through all cofinite entourages of Γ.

Corollary 5.11

If Γ is a cofinite directed graph and R is a cofinite entourage of Γ, then the inclusion map Γ ↪ Γ̄ induces an isomorphism of topological directed graphs Γ/R → Γ̄/R̄.

Example 5.12

Let Γ be a topological directed graph. Suppose that Γ is completely regular so that it is embedded in its Stone–Čech compactification β(Γ); we will regard Γ ⊆ β(Γ). We claim that β(Γ) has a unique topological directed graph structure such that Γ is a sub-directed graph. By the universal property of Stone–Čech compactifications, the source and target maps on Γ extend to continuous maps s, t : β(Γ) → β(Γ) and the extensions are unique. Note that s(s(x)) = s(x) and t(t(x)) = t(x) for all x ∈ β(Γ) since these equations hold for all x in the dense subspace Γ. It is also easy to check that the fixed point sets of s and t in β(Γ) are both equal to V(Γ)¯ (the closure of V (Γ) in β(Γ)). Thus β(Γ) equipped with the unique continuous extensions of the source and target maps of Γ is a topological directed graph with V(β(Γ))=V(Γ)¯, and our claim follows.

Theorem 5.13

Let Γ be a directed graph endowed with its maximal cofinite uniformity. Then β(Γ) is the completion of Γ.

6.1. Cofinite Spaces

A cofinite space is a cofinite directed graph X with V (X) = X. In this case, the source and target maps are equal to the identity map on X, and so are irrelevant. The completion X̄ of a cofinite space X is also a cofinite space since V(X¯)=V(X)¯=X¯ (by Lemma 5.8), and it is compact. Thus X̄ is a profinite space (i.e., a compact Hausdorff totally disconnected space).

6.2. Cofinite Graphs

By a graph we mean a graph in the sense of Serre [5] and Stallings [6]. Thus a graph is a set Γ equipped with a source map s: Γ → Γ and an inversion map⁻¹: Γ → Γ such that for all x ∈ Γ,

The common fixed point set of these two maps is called the vertex set of Γ and is denoted by V (Γ) = {x ∈ Γ | s(x) = x} = {x ∈ Γ | x⁻¹ = x}. For x ∈ Γ, the vertex s(x) is called the source of x and we define the target of x to be the vertex t(x) = s(x⁻¹). We call x⁻¹ the inverse of x. The set E(Γ) = Γ V (Γ) is called the edge set of Γ. In other words, a graph is directed graph equipped with an involution that interchanges sources and targets and whose fixed point set is the vertex set.

A map of graphs is a function f : Γ → Δ between graphs that preserves sources and inverses. It then follows that targets are also preserved, and thus f is also a map of directed graphs.

Let R be an equivalence relation on a graph Γ. We say that R is a graph equivalence relation if Γ/R admits a structure of a graph such that the natural map ν: Γ → Γ/R is a map of graphs. In this case, it is clear that the graph structure on Γ/R is unique and given by: s(R[x]) = R[s(x)], t(R[x]) = R[t(x)], R[x]⁻¹ = R[x⁻¹], and V (Γ/R) = ν(V (Γ)). It is also easy to see that R is a graph equivalence relation if and only if these two conditions hold:

• (1) if (x, y) ∈ R, then (s(x), s(y)) ∈ R and (x⁻¹, y⁻¹) ∈ R; and

• (2) (x, s(x)) ∈ R if and only if (x, x⁻¹) ∈ R.