Applications of infinite graph theory

Question

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 1

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 2

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 3

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 4

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 5

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.

Answer 6

One of applications of infinite Graph theory is about boiling points of infinite symmetric graphs in Nanotechnology .

Wiener showed that the Wiener index number is closely correlated with the boiling points of Alkane molecules see Wiener, H. J. "Structural Determination of Paraffin Boiling Points." J. Amer. Chem. Soc. 69, 17-20, 1947.

Let $G$ be a molecular graph with vertex set $V$. The Wiener index of $G$ which is denoted by $W(G)$ is defined by $\sum_{(u,v)\subset V\times V} d(u,v)$ where $d(u, v)$ denotes the distance between the vertices $u$ and $v$. Wiener index is topological invariant.

In fact Wienere index is invariant under the action of the automorphism group of the graph $G$. So the study of Wiener indices is correspond to study of topological invariant theory of graphs

For example for the case of Carbon Nanocone, which is infinite symmetric graph

In fact Hyper-Wiener index is topological invariant and we calculated(when I was Bachelor degree) the hyper-Wiener index of the infinite one-pentagonal Carbon Nanocone. The graph of this molecule consists of one pentagon surrounded by layers of hexagons. If there are layers, then this graph is denoted by $G_n$

We showed the following explicit formula

$$WW(G_n)=20+\frac{533}{4}n+\frac{8501}{24}n^2+\frac{5795}{12}n^3+\frac{8575}{24}n^4+\frac{409}{3}n^5+21n^6$$

See

M. R. Darafsheh, M. H. Khalifeh and H. Jolany, The Hyper-Wiener Index of One-pentagonal Carbon Nanocone, Current Nanoscience, 2013, 9, 557-560 557

We also computed (when I was Bachelor degree)the Wiener index Dendrimer Nanostar which is infinite graph

We showed the following explicit formula

$$W_{\{G_n\}} = 972n4^n−14584^n+17552^n−270$$

M. H. Khalifeh, M. R. Darafsheh, and H. Jolany, The Wiener, Szeged, and PI Indices of a Dendrimer Nanostar, Journal of Computational and Theoretical Nanoscience Vol. 8, 220–223, 2011

Moreover we computed(when I was bachelor degree) the Wiener index of a phenylenic pattern graph which is infinite symmetric graph.

We showed that

$$W(G_{m,n})= − 4 − 64/5 n + 9m + 24m^3 + 30mn + 48m^3 n + 12m^2n + 24m^3n^2+ 18m^2n^2 − 18n^2 − 14n^3 + 6m^2n^3 + 39mn^2 − 6n^4 − 6/5 n^5 + 24n^3m + 6n^4m$$

See my Bachelor paper

M. R. Darafsheh , H. Jolany & M. H. Khalifeh, Computing the Wiener Index of a Phenylenic Pattern, Fullerenes, Nanotubes and Carbon Nanostructures Volume 19, 2011 - Issue 8

Answer 7

A model of set theory $\langle M,\in\rangle$ is a certain kind of directed graph. So graph theory has the capacity to serve as a foundation of mathematics, having a copy of virtually any conceivable mathematical structure within it.

Answer 8

Example: infinite models rule out certain kinds of proofs. If you are interested in a property $P$, formulated in the first-order logic of graph theory, and if you can prove the existence of an infinite graph satisfying $P$, then this proves that a conjecture of the form $C(P)$="there does not exist a finite graph satisfying $P$" can never be proved by reasoning with (0) the axioms of the language of graph theory, (1) your statement $P$, (2) the usual inference rules of first-order logic.

In this sense, awareness of infinite graphs can have a very practical consequence: you then know that $C$ cannot be proved this way, and---if at all---you will only ever prove it by making essential use of the finiteness of the vertex set.

This may appear tautological in this generality, but in practice, it can have real value.

Example: there is an (in)famous open problem about finite triangle-free graphs, where, for each $n\in\mathbb{N}$,

$P:=P(n):=$"the graph is triangle-free, and is triangle-freeness-preservingly $n$-existentially-closed".

This predicate is easily expressed in the first-order logic of graph theory; the latter property is often abbreviated $n$-e.c. in the literature. Being triangle-freeness-preservingly so means that of course only those extension-properties are required to hold which do not immediately create a triangle.

Then $C(P)$ is known to be false for each⁰ $n\in4$, in view of explicitly known (and even infinite) families of finite graphs satisfying $P(n)$. Up to an including $n=3$, many such graphs are known, though they appear not to be completely classified^1,2. But the truth-value of $C(P(4))$ is notoriously open; the most direct approach would be to say "Hey let's go and write $F:=$"the graph is triangle-free", and $E(n):=$the graph is triangle-freeness-preservingly $n$-e.c.", note $P(n)=F\wedge E(n)$, and prove $C(P(4))$ by simply proving via first-order inference-rules that $E(4)\Rightarrow\neg F$." It is not clear a priori that this attempt might not simply work, with the first-order derivations being maybe a bit long, but manageable---however, this way ,the mission will be impossible: in a famous paper³ Henson proved that there exists a countably-infinite triangle-free graph which is triangle-freeness-preservingly $4$-e.c. (and much more than that). Therefore, the (conjectural) $C(P(4))=\mathrm{true}$ cannot be proved in the above straightforward way. Here, infinite graphs prevent you from attempting the impossible, and help you focus on trying other methods of proof. If you would not be aware of the concept of infinite graphs, e.g. by being taught that all graphs are finite, this argument would not be available to you.

_Footnotes.

_{0. Needless to say, for $n=0\in4$, we have $P(0)$ $=$"the graph is triangle-free", and it is evidently false that there does not exist a finite graph satisfying $P(0)$.}

_{1. G. Cherlin, Two problems on homogeneous structures, revisited. In: Model Theoretic Methods in Finite Combinatorics, M. Grohe and J.A. Makowsky eds.,Contemporary Mathematics, 558, American Mathematical Society, 2011, and also}

_{2. C. Even-Zohar and N. Linial: Triply Existentially Complete Triangle-Free Graphs. J. of Graph Theory, 78 (4), 2015, 305--317}

_{3. C. W. Henson. A family of countable homogeneous graphs, Pacific Journal of Mathematics, 38 (1971) 69–83}

Answer 9

In addition to the aforementioned many applications outside graph theory, another reason for caring about infinite graphs is that they are helpful for proving results about finite graphs. The papers below give some examples.

László Babai Vertex-transitive graphs and vertex-transitive maps https://onlinelibrary.wiley.com/doi/10.1002/jgt.3190150605

Justin Salez Sparse expanders have negative curvature https://arxiv.org/abs/2101.08242

Martin Grohe, Pascal Schweitzer, Daniel Wiebking, Automorphism groups of graphs of bounded Hadwiger number https://arxiv.org/abs/2012.14300

A short proof of Fleischner’s theorem https://www.sciencedirect.com/science/article/pii/S0012365X09003355 was found via another excursion into the infinite.

According to this wikipedia article https://en.wikipedia.org/wiki/Halin%27s_grid_theorem, Halin's grid theorem "is a precursor to the work of Robertson and Seymour linking treewidth to large grid minors", which if true provides perhaps the best example of how infinite graphs help you in the study of finite ones.