34
$\begingroup$

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?

$\endgroup$
8
  • 7
    $\begingroup$ To study percolation you basically need an infinite graph to avoid finite-size effects. $\endgroup$ Sep 22, 2010 at 19:45
  • 6
    $\begingroup$ 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? $\endgroup$ Sep 22, 2010 at 19:48
  • 4
    $\begingroup$ Random walks or harmonic functions aren't as interesting for finite graphs. $\endgroup$ Sep 22, 2010 at 20:00
  • 5
    $\begingroup$ 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. $\endgroup$ Sep 22, 2010 at 20:02
  • 6
    $\begingroup$ 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. $\endgroup$
    – Terry Tao
    Sep 22, 2010 at 22:23

9 Answers 9

28
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ @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. $\endgroup$ Sep 22, 2010 at 21:29
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 22, 2010 at 22:05
  • $\begingroup$ @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? $\endgroup$ Sep 23, 2010 at 9:49
  • $\begingroup$ @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. $\endgroup$ Sep 23, 2010 at 16:08
  • $\begingroup$ Isn't the proof itself of KIL itself almost a tautology? $\endgroup$
    – Qfwfq
    Jun 9, 2017 at 16:34
17
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 23, 2010 at 0:46
  • 6
    $\begingroup$ 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. $\endgroup$ Sep 23, 2010 at 5:58
13
$\begingroup$

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

$\endgroup$
1
  • 6
    $\begingroup$ Published by Springer as "Trees." $\endgroup$ Sep 22, 2010 at 21:33
12
$\begingroup$

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.

$\endgroup$
2
  • 5
    $\begingroup$ 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... $\endgroup$ Sep 23, 2010 at 0:19
  • $\begingroup$ @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... $\endgroup$ Sep 23, 2010 at 9:51
9
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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 enter image description here

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 graphenter image description here

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.enter image description here

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

$\endgroup$
2
  • 9
    $\begingroup$ These appear to be nice examples of what one could call conceptually infinite models. While developed with a view towards things to which the word "finite" is often applied (whatever that means), it is more useful not to introduce the complication of actually assuming a mathematical finiteness-hypothesis. Sometimes people speak of avoiding boundary effects in that regard. $\endgroup$ Jun 9, 2017 at 19:18
  • $\begingroup$ Additional comment: Study of Topological indices like Wiener index , Hyper-Wiener index used in sociometry and the theory of social networks. See the interesting paper of Christophe Soulé about it ihes.fr/~soule/knock.pdf $\endgroup$
    – user21574
    Dec 1, 2017 at 20:17
4
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Yes and no: such a model is a well-founded tree in the set-theorists' sense of tree. This sense is different from the graph-theorists' sense of tree. Not that there would be anything wrong with that. $\endgroup$ Jun 9, 2017 at 18:11
  • 1
    $\begingroup$ No, a model of set theory is not a tree, in anyone's sense. (And a model of set theory needn't be well-founded). But $\in$ is a directed binary relation, which makes it a directed graph. $\endgroup$ Jun 9, 2017 at 18:15
  • 1
    $\begingroup$ Right, thanks for pointing out, the comment conflated "model of set theory" with "(classifying set of) a class of sets often studied in set-theory". For example, $\Pi_1^1$-sets are often classified by well-founded trees. $\endgroup$ Jun 9, 2017 at 18:35
3
$\begingroup$

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 each0 $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 classified1,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 paper3 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

$\endgroup$
6
  • $\begingroup$ In the first paragraph, "there does not exist a finite graph satisfying P" is not even a statement of first-order logic, so I would clarify what you mean by a conjecture of that form. $\endgroup$
    – user44143
    Jun 9, 2017 at 16:35
  • 1
    $\begingroup$ @MattF.: $C(P)$ was not claimed to be a first-order statement. You are right that it is not. But the point is somewhere else. As to the clarification you request: $C(P)$ means, well, what it says. In the example, it means: "there does not exist any finite graph which has the first-order property being triangle-free and being triangle-freeness-preservingly-$4$-existentially-closed". It is not known afaik whether this conjecture is true. $\endgroup$ Jun 9, 2017 at 17:28
  • $\begingroup$ And, in short, what the infinite graphs do for your is that they rule out the a priori possibility that the first-order property being triangle-free and being triangle-freeness-preservingly-4-existentially-closed is outright inconsistent. If you write out the latter property (the one in italics) in first-order logic, it is sufficiently complex that it seems fair to say that it is not humanly possible to tell right away whether it may just be inconsistent, i.e., that its negation be a validity on the class of all graphs. The infinite models show that it is not inconsistent. $\endgroup$ Jun 9, 2017 at 17:30
  • $\begingroup$ And the negation of the first-order property in italics, while not a validity on the class of all (simple undirected) graphs, may be a validity on the class of all finite graphs. This is the open conjecture. $\endgroup$ Jun 9, 2017 at 17:35
  • 1
    $\begingroup$ And, explicitly, because of $P(4)=F\wedge E(4)$, a first-order proof of $E(4)\Rightarrow\neg F$, i.e., a proof that the property being triangle-freeness-preservingly-$4$-e.c. implies the existence of a triangle, would be a proof that $P(4)$ is simply inconsistent (and hence that $C(P(4))$ would be true for the strong reason that there does not exist any graph with $P(4)$, not only no finite one). The infinite models tell you that it is not that easy. $\endgroup$ Jun 9, 2017 at 18:01
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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