27
$\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$
  • 5
    $\begingroup$ To study percolation you basically need an infinite graph to avoid finite-size effects. $\endgroup$ – Eric Tressler Sep 22 '10 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$ – Qiaochu Yuan Sep 22 '10 at 19:48
  • 4
    $\begingroup$ Random walks or harmonic functions aren't as interesting for finite graphs. $\endgroup$ – Gjergji Zaimi Sep 22 '10 at 20:00
  • 4
    $\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$ – Owen Sizemore Sep 22 '10 at 20:02
  • 5
    $\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 '10 at 22:23
24
$\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$
  • 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$ – Pete L. Clark Sep 22 '10 at 21:29
  • 1
    $\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$ – John Stillwell Sep 22 '10 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$ – Pete L. Clark Sep 23 '10 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$ – John Stillwell Sep 23 '10 at 16:08
  • $\begingroup$ Isn't the proof itself of KIL itself almost a tautology? $\endgroup$ – Qfwfq Jun 9 '17 at 16:34
16
$\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$
  • $\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$ – Per Vognsen Sep 23 '10 at 0:46
  • 4
    $\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$ – Péter Komjáth Sep 23 '10 at 5:58
12
$\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$
  • 6
    $\begingroup$ Published by Springer as "Trees." $\endgroup$ – Qiaochu Yuan Sep 22 '10 at 21:33
11
$\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$
  • 4
    $\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$ – Joel David Hamkins Sep 23 '10 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$ – Pete L. Clark Sep 23 '10 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$
  • 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$ – Peter Heinig Jun 9 '17 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 '17 at 20:17
3
$\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$
  • 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$ – Peter Heinig Jun 9 '17 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$ – Joel David Hamkins Jun 9 '17 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$ – Peter Heinig Jun 9 '17 at 18:35
2
$\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$
  • $\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$ – Matt F. Jun 9 '17 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$ – Peter Heinig Jun 9 '17 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$ – Peter Heinig Jun 9 '17 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$ – Peter Heinig Jun 9 '17 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$ – Peter Heinig Jun 9 '17 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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