Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A (directed) graph $\Gamma$ is usually defined as a pair $(V,E)$ where $V$ is the set of vertices and $E \subseteq V \times V$ is the set of edges. A morphism of graphs $\Gamma$ and $\Gamma'$ is then a mapping $\varphi: V \to V'$ such that $(x,y) \in E$ implies $(\varphi(x), \varphi(y)) \in E'$.

I'm interested in thinking about inverse limits of (finite) graphs, ie. profinite graphs. Any time I see such a thing mentioned an alternative definition of a graph (due to Serre?) is usually used: A graph $\Gamma$ consists of a set $V$ of vertices, a set $E$ of edges and a mapping $\delta: E \to V \times V$, $x \mapsto (\delta_1(x), \delta_2(x))$. A morphism $\Gamma \to \Gamma'$ here is a pair of maps $\varphi_v: V \to V'$ and $\varphi_e: E \to E'$ such that $\delta_i(\varphi_e(e)) = \varphi_v(\delta_i(e))$ for all $e \in E$.

Is there any reason why we can't talk about an inverse system of graphs using the first definition and look at inverse limits of these? Perhaps something obvious breaks down that I'm just not seeing.

share|improve this question
The alternate definition allows multiple edges between nodes and edges between a node and itself. –  Thomas Andrews Feb 13 '12 at 14:31
Thomas, both representations allow edges between a node and itself. The only difference is multiple edges. –  JDH Feb 13 '12 at 14:46
I think Serre's definition is really taylored in order to make sure that Cayley graphs of profinite groups are profinite graphs. I have been studying inverse limits of undirected graphs for a while, but not with respect to homomorphisms but rather maps that preserve both edges and non-edges unless they identify to vertices. This is a kind morphism between graphs that doesn't prefer edges over non-edges and that is related to modular decompositions of graphs. –  Stefan Geschke Jun 4 '13 at 12:06
add comment

2 Answers

up vote 2 down vote accepted

No, no reason why you cannot do that. To be sure, any time you have a category, you can talk about inverse limits (or, more generally, limits), and your first definition is easily seen to be a category. Let us call that $\mathbf{Grph_1}$ and the second category $\mathbf{Grph}$. As mentioned in JDH's answer, the only difference between the two is that the first does not allow multiple edges between a pair of vertices, so $\mathbf{Grph_1}$ is a (full) subcategory of $\mathbf{Grph}$.

The more pressing question is probably whether (inverse) limits in $\mathbf{Grph_1}$ will exist and be the same as (inverse) limits in $\mathbf{Grph}$ (since those are the ones you've seen described); if you can answer the second question in the positive, the first one follows. My guess (I haven't checked the details) is that it is true: morphisms in these categories are the same, so the only thing that could go wrong is if an (inverse) limit, taken in $\mathbf{Grph}$, of objects in $\mathbf{Grph_1}$ is not an object in $\mathbf{Grph_1}$, so it is sufficient to simply check that this never happens.

As an aside, I'll mention that one advantage of $\mathbf{Grph}$ in this respect is that it can be realized as a functor category $\mathbf{Set}^{C}$, i.e. the category of functors $C \to \mathbf{Set}$, where $\mathbf{Set}$ is the category of sets and $C$ is a category with two objects $\{1\}$ and $\{2\}$ and two (non-identity) morphisms $\{1 \} \to \{2 \}$. As such, it automatically has all (small) limits because $\mathbf{Set}$ has all (small) limits.

share|improve this answer
I guess that collapsing parallel edges gives a reflection from $\mathbf{Grph}$ to $\mathbf{Grph_1}$, so the inclusion of $\mathbf{Grph_1}$ into $\mathbf{Grph}$ preserves (inverse) limits. –  Marc Olschok Feb 14 '12 at 14:43
add comment

Your two graph representation methods do not give rise to exactly the same concept of graph, even apart from the inverse limit question.

In the first representation, you are thinking of an edge as a relation on pairs of vertices. In the second representation, you are thinking of edges as distinct objects, and the map $\delta$ tells you how the edges interact with the vertices.

One main difference is that the first representation, using $(V,E)$ with $E\subset V\times V$, does not allow you to represent graphs having multiple edges between the same two vertices, because two vertices are either related by $E$ or they are not. It doesn't make sense in that representation for them to be related more than once.

In the second case, however, you can easily represent multiple edges between the same two vertices, simply by adding more edge objects, and having $\delta$ connect them to the same pair of vertices.

The inverse limit concept applies to either notion of graph, but of course the categories are different.

The are quite a few different graph concepts--directed graphs, undirected, graphs with loops (edges connecting a vertex to itself), loopless graphs, multiple edges, etc.---and in treating many general questions about the category of all graphs, it it sometimes important to take care to state specifically which kind of graph one has in mind. Thus, one arrives at different representations such as those you mention here.

share|improve this answer
Good point, thank you. Assuming multiple edges are disallowed, will the two representations give the same projective limit? –  Bob Heffernan Feb 13 '12 at 13:49
Yes, in that case there is an isomorphism of the representations, which commutes with your morphisms. –  JDH Feb 13 '12 at 14:01
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.