# Applications of infinite graph theory

Finite graph theory abounds with applications inside mathematics itself, in computer science, and engineering. Therefore, I find it naturally to do research in graph theory and I also clearly see the necessity.

Now I'm wondering about infinite graph theory. Quite a bit of research seems to be done on it as well and of course they are a natural generalization of a useful concept. But I never saw an example where we actually need them.

I understand that they come up as infinite Cayley graphs in group theory, that the automorphism groups of infinite but locally finite graphs are topological groups, that they play some role in general topology, etc. But to me it seems they are "just there" and are not essential in the sense that a theorem about them proves something about groups or topology what we couldn't have done easily without using them.

Polemically phrased my question is

Why should we care about infinite graphs?

-
To study percolation you basically need an infinite graph to avoid finite-size effects. – Eric Tressler Sep 22 '10 at 19:45
The universal cover of a d-regular finite graph is the d-regular infinite tree. If you care about d-regular finite graphs (e.g. expanders) then you should care about the d-regular infinite tree, right? – Qiaochu Yuan Sep 22 '10 at 19:48
Random walks or harmonic functions aren't as interesting for finite graphs. – Gjergji Zaimi Sep 22 '10 at 20:00
There is a simple proof that every subgroup of a free group is free using infinite graphs and covering spaces. While a purely algebraic proof is not so easy. More generally many interesting facts about groups can be proven based on the fact that they act nicely on infinite graphs. – Owen Sizemore Sep 22 '10 at 20:02
In the converse direction, one can view infinite graphs as a discretisation of continuous spaces (and infinite Cayley graphs as a discretisation of homogeneous spaces). Gromov's original proof of his theorem relies on this perspective (or more precisely, the idea that homogeneous spaces can arise as limits of infinite Cayley graphs). So the discrete infinitary theory of infinite graphs form a nice bridge between the discrete finitary world and the continuous infinitary world. – Terry Tao Sep 22 '10 at 22:23

## 5 Answers

The first book on graph theory was König's Theorie der endlichen und unendlichen Graphen (Theory of finite and infinite graphs) of 1936. Thus infinite graphs were part of graph theory from the very beginning. König's most important result on infinite graphs was the so-called König infinity lemma, which states that in an infinite, finitely-branching, tree there is an infinite branch. This lemma encapsulates many arguments -- from the Bolzano-Weierstrass theorem, to the completeness theorem of logic, to the proof of various Ramsey theorems -- in graph-theoretic form. König himself used it to prove that the infinite form of van der Waerden's theorem on arithmetic progressions implies the finite version, and Erdos and Szekeres (who were students of König) took up the idea in their pioneering 1935 paper on Ramsey theory.

As other commentators have mentioned, infinite graphs are also important as group diagrams in combinatorial group theory and low-dimensional topology.

-
@JS: I knew about König's infinity lemma before -- I use it in an article on factorization to give a (third!) proof that ACC on principal ideals implies the existence of factorizations into irreducibles. But I don't know about the relationship between KIL and most of the applications you give: I find the prospect of a connection to Bolzano-Weierstrass and Godel Completeness especially intriguing. Could you perhaps say a little more and/or give references for this? Thanks very much. – Pete L. Clark Sep 22 '10 at 21:29
Pete, I see Bolzano-Weierstrass and the completeness theorem as instances of KIL because in both one finds a desired object as an infinite branch in a tree. In Bolzano-Weierstrass one finds a limit point of an infinite set in [0,1] via the "tree" of subintervals obtained by bisection. In the completeness theorem one tries to falsify a formula by building a tree of subformulas. If all branches terminate, one gets a proof; if not, an infinite branch gives a falsifying assignment. One book that proves completeness this way, IIRC, is Smullyan's First-order Logic. – John Stillwell Sep 22 '10 at 22:05
@John: thanks for your comment. I thought a bit more about the proof of Bolzano-Weierstrass, and while I do see a place to apply KIL, I would have thought that in this case the conclusion was obvious. So I think I'm still missing out on the real connection between BW and KIL. Or are you just saying that BW is one of many results in which one can see, if one is so inclined, an infinite, finitely branching tree which necessarily contains an infinite path, and that this path exists is useful? – Pete L. Clark Sep 23 '10 at 9:49
@Pete: Yes, the BW theorem is definitely at the easy end of the spectrum of results that follow from KIL. I mentioned it only as one of many results, some of which are much less obvious, that have the same logical strength as KIL. Steve Simpson's book Subsystems of Second-order Arithmetic gives many more such results. Another one I like is the Brouwer fixed point theorem. – John Stillwell Sep 23 '10 at 16:08

Here's a nice proof of the Cantor-Bernstein theorem in the language of infinite graphs.

Theorem. Let $G$ be an infinite graph with bipartition $(A,B)$. If $G$ has a matching saturating $A$ and a matching saturating $B$, then $G$ has a perfect matching.

Proof. Let $M_A$ and $M_B$ be matchings saturating $A$ and $B$ respectively. Let $H$ be the graph with vertex set $A \cup B$ and edge set the (disjoint) union of $M_A$ and $M_B$. Hence $H$ may be a multigraph. It is easy to check that every component of $H$ is either an infinite path or an even cycle. Thus, taking every other edge of each component of $H$ yields a perfect matching of $G$.

-
I first learned that proof from Conway and Doyle's paper Division by Three where they phrase it in terms of colors. It is the only proof of Cantor-Bernstein that I really understand at a gut level. – Per Vognsen Sep 23 '10 at 0:46
I think this proof originates from Julius Konig, Sur la theorie des ensembles, Comptes Rendus, 143(1906), 110-112. The explicit use of infinite graphs was added in Konig junior's book. – Péter Komjáth Sep 23 '10 at 5:58
Thanks for the reference Peter. – Tony Huynh Sep 23 '10 at 18:17

Bass--Serre theory translates the algebraic notion of a `splitting' of a group $G$ into an action of $G$ on a (usually infinite) tree. See Serre's classic Arbres, Amalgames, $SL_2$.

-
Published by Springer as "Trees." – Qiaochu Yuan Sep 22 '10 at 21:33

The Rado graph (or countable random graph) is graph theory's answer to the normal distribution. It seems almost any sensible definition of drawing edges on a countable graph 'randomly' or even 'pseudo-randomly' will almost surely produce the Rado graph. The study of this specific graph (and similar 'universal' entities) could be justified simply by its ubiquity. That said, I don't know if it's had any clear applications to other areas.

-
The random graph illustrates in a single structure a number of fundamental ideas of model theory: quantifier elimination, saturation, back-and-forth partial isomorphisms, categoricity... – Joel David Hamkins Sep 23 '10 at 0:19
@Joel: Sigh. You're right, and yet when I taught a course on model theory this summer, I didn't mention it. Can't win them all, I suppose... – Pete L. Clark Sep 23 '10 at 9:51

Recently there has been quite a bit of activity in descriptive set theory concerning definable graphs. Benjamin Miller derived several deep classical results such as Silver's theorem (stating that every sufficiently nice (here coanalytic) equivalence relation on a separable complete metric space either has countably many equivalence classes or there is a Cantor space of pairwise non-equivalent points) from results on uncountable graphs by relatively elementary proofs. The original proof of Silver's theorem used heavy set-theoretic machinery.

The result on uncountable graphs that started it all is the $\mathcal G_0$-dichotomy of Kechris, Solecki and Todorcevic:

There is a closed graph $\mathcal G_0$ on the Cantor space such that for every analytic graph $G$ on a Polish space either $G$ has a Borel-measurable coloring with countably many colors or there is a graph homomorphism from $\mathcal G_0$ to $G$.

So in some sense, $\mathcal G_0$ is the minimal analytic graph whose Borel-chromatic number is uncountable.

-