Applications of infinite graph theory - MathOverflow

Applications of infinite graph theory

2010-09-22T19:39:37Z

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?

Answer by John Stillwell for Applications of infinite graph theory

2010-09-22T21:06:08Z

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.

Answer by HW for Applications of infinite graph theory

2010-09-22T21:28:08Z

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$*.

Answer by Colin Reid for Applications of infinite graph theory

2010-09-22T22:12:09Z

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.

Answer by Tony Huynh for Applications of infinite graph theory

2010-09-22T22:26:41Z

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$.

Answer by Stefan Geschke for Applications of infinite graph theory

2010-09-23T09:26:46Z

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.