Cofinite graphs and cofinite groupoids are defined in a unified way extending the notion of cofinite group introduced by Hartley. These objects have in common an underlying structure of a directed graph endowed with a certain type of uniform structure, called a cofinite uniformity. Much of the theory of cofinite directed graphs turns out to be completely analogous to that of cofinite groups. For instance, the completion of a directed graph Γ with respect to a cofinite uniformity is a profinite directed graph and the cofinite structures on Γ determine and distinguish all the profinite directed graphs that contain Γ as a dense sub-directed graph. The completion of the underlying directed graph of a cofinite graph or cofinite groupoid is observed to often admit a natural structure of a profinite graph or profinite groupoid, respectively.
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
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
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.
Let Γ be the directed graph obtained by subdividing the real line at the integer points, so
For each integer
For integers 0 ≤
Embed Γ in Γ̂_{1} via the canonical map of directed graphs determined by the compatible family of maps
Thus Γ̂_{1} and Γ̂_{2} 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 Γ̂
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.
Let Γ be a connected, locally finite directed graph (see [6]). For each finite sub-directed graph ∑ of Γ, let
1. If ∑_{1},∑_{2} ∈
2. For every
3. ∩_{∑}
Hence the set {
We do not distinguish between a binary relation and its graph. Thus, by a
The
The following lemma identifies certain equivalence relations on topological spaces that are useful in describing the uniform structure of profinite spaces. Recall that the
(1)
(2)
(3)
By the corollary to Proposition 4 of [1, Section I.4.2], (1) ⇒ (2). Being an equivalence relation,
which makes it clear that (2) ⇒ (1). Note also that (2) ⇔ (3) since points are open in
The
1. (
2.
3. if
A
A subset ∑ of a directed graph Γ is called a
Let (Γ
A
An equivalence relation
If
is clearly a compatible equivalence relation on Γ.
On the other hand, if
Moreover, we have this
The intersection of a non-empty family of compatible equivalence relations on a directed graph Γ is again a compatible equivalence relation on Γ. Thus, given any subset
A
Every sub-directed graph of a topological directed graph will be regarded as a topological directed graph with the subspace topology. Likewise, if
A
Recall that every compact Hausdorff space
For this purpose, we make use of the following observation.
Let
is a clopen subset of
By replacing
However
To describe the uniform structure of profinite directed graphs and their sub-directed graphs, it is convenient to make the following definition.
(Cofinite entourage) Let Γ be a directed graph endowed with a uniformity. A
It should be noted that a directed graph Γ endowed with a uniformity always has at least one cofinite entourage, namely
(1)
(2)
(3)
(4)
(5)
(6)
We are now ready to give our characterization of profinite directed graphs in terms of their uniform structures.
Suppose first that Γ is a profinite directed graph and let
Then
(i)
(ii)
(iii)
Hence
Conversely, assume now that the non-empty set, say
We observe now that Theorem 3.4 provides a canonical realization of a profinite directed graph Γ as a projective limit of finite directed graphs. Let
Moreover, (Γ
Therefore
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
(Cofinite directed graph) A
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.
Let
and thus
We always endow a cofinite directed graph with the topology induced by its uniformity, and as we just observed, this makes it into a Hausdorff topological directed graph. This topology can be characterized as follows.
Let Γ be a cofinite directed graph and let
and each
and each
As we noted above, every sub-directed graph of a profinite directed graph is a cofinite directed graph when it is endowed with its relative uniformity. On the other hand, cofinite directed graphs can be constructed from scratch as follows.
Let Γ be any abstract directed graph and let
Then
Amongst all uniform structures of this type that can be put on Γ, there is a unique maximal one, namely that in which
Let
Now let
We see that every singleton subset {
It would be interesting to know which other filter bases
(1) Γ
(3) Γ
(2) ∩
(1) ⇒ (2): Let
(2) ⇒ (3): Let
(3) ⇒ (1): We have that
Consequently, we see that every cofinite directed graph Γ is totally disconnected and that the intersection of all of its cofinite entourages is equal to the diagonal
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
Being compact and Hausdorff, Δ is a complete uniform space. So there exists a unique uniformly continuous map
Since
Based on the theorem above, we make the following definition.
(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
As an immediate consequence of Theorem 5.1, we have the following result on uniqueness of completions.
We turn now to the question of existence of completions. Let Γ be a cofinite directed graph and let
For each
(i)
(ii)
Hence we have an inverse system of (finite discrete) topological directed graphs and (surjective) continuous maps of directed graphs (Γ
Let
With this setup, we make the following observation.
For each
Since Γ is Hausdorff, ker
Finally, note that for each
Combining these observations we obtain the following result.
(Existence and uniqueness of completions)
Since a compact Hausdorff space (endowed with its unique compatible uniformity) is complete, this follows from [1, II. 3.6, Theorem 2].
In the definition of the completion of a cofinite directed graph Γ, we did not require that Γ̄ is a cofinite directed graph. However, it turns out that this is automatically true. In proving this and other things, we modify our notation as follows.
From now on, if
We first prove a couple of lemmas.
Since
It follows from this lemma that if Γ is a cofinite directed graph and ∑ is a sub-directed graph (endowed with the relative uniformity), then ∑̄ (endowed with the relative unifrormity) is the completion of ∑.
The natural map
First note that
since
Let
Now let
Let
and
Let Γ be a topological directed graph. Suppose that Γ is completely regular so that it is embedded in its Stone–Čech compactification
By Proposition 4.3, Γ is discrete. So
Applying Theorem 3.4, we see that the set of all cofinite entourages of
On the other hand, suppose that
It follows that Γ is uniformly embedded in
A
By a graph we mean a graph in the sense of Serre [5] and Stallings [6]. Thus a
The common fixed point set of these two maps is called the
A
Let
(1) if (
(2) (
(Cofinite graph) Let Γ be a graph endowed with a uniformity. A
In particular, a cofinite graph Γ is a cofinite directed graph. So by Lemma 4.2, the source and target maps of a cofinite graph Γ are uniformly continuous, and by a similar argument, its involution is also uniformly continuous. Thus Γ is a Hausdorff topological graph (i.e., a graph endowed with a topology such that the source, target, and inversion maps are all continuous). Furthermore, by Theorem 5.10, its completion Γ̄ as a cofinite directed graph is a profinite directed graph. We show next that there is a unique involution on Γ̄ making it into a cofinite graph such that Γ is a subgraph (i.e., a sub-directed graph closed under the involution).
Let Γ̄^{Reverse} be the topological directed graph with the same underlying topological space as Γ̄ but with source and target maps interchanged. Then the map Γ → Γ̄^{Reverse} given by
It remains to show that the fixed set
To establish the second part, it suffices (by Theorem 5.10) to show that for each cofinite entourage
By Theorem 6.2, Γ̄ is a cofinite graph, and thus a topological graph. Moreover, it is compact, Hausdorff, and totally disconnected by Theorem 5.10.
It is easy to see that a cofinite graph Γ is compact if and only if it is isomorphic to the inverse limit of an inverse system of finite discrete topological graphs and continuous maps of graphs. Such cofinite graphs are called
Above we saw that the completions of cofinite spaces and cofinite graphs are profinite spaces and and profinite graphs, respectively. We will see that the situation for cofinite groupoids is more complicated in general.
To begin with, we review some basic groupoid theory. Recall that a groupoid is a small category in which every arrow is invertible. To be more precise, a
1.
2. if
3.
4. there exists
Customarily the set of composable pairs in a groupoid
Then the partial binary operation on
A groupoid
Given any groupoid
If
A subset
(1)
(2) if
(3)
In this case,
The
An equivalence relation
(1) if (
(2) if (
(3) if (
However, in this situation, the quotient of the underlying directed graph
To avoid this difficulty, we restrict our attention to a certain type of congruences that behave better. To describe these, we make use of the following notation. If Γ is any directed graph (for example, a groupoid) and
By a -
Let
Note that a cofinite groupoid has an underlying cofinite directed graph structure, and thus has uniformly continuous source and target maps by Lemma 4.2. We observe next that the same goes for the involution and partial product maps.
Since the cofinite congruences
In particular, it follows from Lemma 6.5 that a cofinite groupoid is a Hausdorff topological groupoid. Recall that a
Every subgroupoid
It is clear that each vertex group of a topological groupoid is a topological group. For cofinite groupoids we can say even more.
Since
The set {
Note that every cofinite groupoid
Let
Construct
The following corollaries of Theorem 6.8 are worth noting. The first is an immediate consequence.
By the proof of Theorem 5.9,
Conversely, let
The set
We will see that cofinite groupoids with only finitely many vertices behave very much like cofinite groups in many regards. To start with, we make a convenient definition.
We say that a congruence
There is an equivalent alternative approach to rigid congruences using normal subgroups. Notice that if
In order for a groupoid to have rigid congruences of finite indexes, its vertex set must be finite. And in this case, we make the following very useful observation.
We are assuming that
Extending a property of cofinite groups, we next observe that every cofinite groupoid with only finitely many vertices is completely determined by its topological groupoid structure.
Suppose that the
Note that
We have seen that the topology on
Conversely assume that
For the last part, consider any cofinite groupoid structure on
Viewing groups as groupoids with a single vertex, we obtain the following result as an immediate corollary.
The following is a refinement of Theorem 6.8 for cofinite groupoids with finite vertex sets.
By Lemma 5.8,
We conclude by briefly sketching an application of the theory of completions of cofinite groupoids which we explore in greater detail in a subsequent paper. Initially, let Γ be a finite discrete graph and let
Although this construction only requires the vertex set of Γ to be finite, we will only be applying it to finite graphs in what follows.
By Theorem 6.15,
Next let
Moreover, if
Let Γ be any profinite graph and let
It should be noted that when Γ is a finite graph, this latter definition of
Turning to induced homomorphisms, we sketch a proof of the following result.
Let
For each
Since
The family of maps (
Let
Now by Steps 1 and 2, the homomorphism
It is now an easy exercise to show that the functorial properties hold in general for induced homomorphisms:
1. If
2. If Γ, Δ, and Ω be profinite graphs and