# Why should “graph theory be part of the education of every student of mathematics”?

Until recently, I thought that graph theory is a topic which is well-suited for math olympiads, but which is a very small field of current mathematical research with not so many connections to "deeper" areas of mathematics.

But then I stumbled over Bela Bollobas "Modern Graph Theory" in which he states:

The time has now come when graph theory should be part of the education of every serious student of mathematics and computer sciences, both for its own sake and to enhance the appreciation of mathematics as a whole.

Thus, I'm wondering whether I should deepen my knowledge of graph theory. I find topics like spectral and random graph theory very interesting, but I don't think that I am ever going to do research on purely graph theoretic questions. To the contrary, I'm mainly interested in areas like algebraic topology, algebraic number theory and differential topology, and I'm wondering if its useful to have some knowledge of graph theory when engaging in these topics.

So my question is: Why should students like me, which are aspiring a mathematical research carreer in mathematical areas which are not directly related to graph theory, study graphs?

-
I have a really basic basis on graph theory from a course I had as an undergraduate, only one brief topic, and I also would like to hear what people has to say about this. –  Marra Apr 26 '13 at 20:45
Topology, algebraic geometry , and number theory come together when one studies Dessins D'enfants. See en.wikipedia.org/wiki/Dessin_d%27enfant –  Baby Dragon Apr 26 '13 at 21:21
Also graphs are easy enough to define and think about, but are complicated enough that almost anything can be phrased in grapg theory. –  Baby Dragon Apr 26 '13 at 21:23
Are you surprised to see a graph theory book selling graph theory as an essential tool? (Regardless the truthfulness of this proposition...) –  Asaf Karagila Apr 26 '13 at 22:08

If you're more interested in algebraic topology, I suggest not to spend much time studying the combinatorial aspects of graph theory. It is true that graphs in this guise do appear in such areas; for instance, one uses Dynkin diagrams (which are graphs) to classify algebraic groups and also Lie groups. It's really very elegant and useful for work in algebraic groups, but you need very little graph theory for this. Graphs are often used where there is some combinatorial structure, but again I doubt (but perhaps I am wrong) that knowing lots of graph theory (as one would find in the typical book like Bondy's) would help too much.

"Graph theory" covers much more than just this, however. For instance an esperantist family (generalisation of expander family) of graphs arise naturally as a certain family of Cayley graphs associated to finite groups that are quotients of fundamental groups (as Riemann surfaces) of algebraic curves, which come from any family of etale covers. This can be used to prove interesting results about families of various arithmetic objects and how they behave generically.

An excellent starting point for these topics is the paper by Ellenberg, Hall, and Kowalski, "Expander graphs, gonality, and variation of Galois representations". This source hopefully should spark your imagination about such topics and encourage you to read up on such topics.

The kind of graph theory covered in a typical undergraduate course I think isn't so prevalent in every day algebraic topology and related fields since the stuff in "typical graph theory" studies properties that aren't invariant under homotopy, and homotopy invariants is the stuff that algebraic topology is built upon. There is however, a kind of "graph theory" that is extremely useful in topology and number theory: it's the theory of simplicial sets (and simplicial objects in any category)! This doesn't just look at graphs though, but objects that are built from higher simplicies too. The basic theory of simplicial objects in algebraic topology covers homotopy-type stuff. Simplicial objects, for instance simplicial sets, are completely combinatorially-defined. For instance "nice" simplicial sets called fibrant ones have a notion of fundamental group and there is a functor from simplicial sets to spaces called "geometric realization" that sends a simplicial set to a space, which for a graph would be the obvious topological space, and the notion of fundamental group agrees with the combinatorially defined one.

Simplicial sets are so fundamental to many areas of algebra such as: $K$-theory (they are typically used to define the higher $K$-groups), higher category theory (which is a generalisation of category theory and also has applications to $K$-theory), homological algebra (essential tool, the cat of nonnegative chain complexes of $R$-modules is equivalent to the category of simplicial objects in the category of $R$-modules), algebraic topology itself of course, algebraic geometry (for things like $\mathbb{A}^1$ homotopy theory), and tons more stuff that I don't know about I'm sure.

Good sources for simplicial objects are:

• May, "Simplicial Objects in Algebraic Topology"
• Ch. 8 of Weibel's "An Introduction to Homological Algebra" (you probably should start here!)
• Goerss's book "Simplicial Homotopy Theory"
• Moerdijk and Toen's "Simplicial Methods for Operads and Algebraic Geometry" (Part 2 is about algebraic geometry)
• Ferrario and Piccinini's "Simplicial Structures in Topology" (more topology)
-

The only reason is that it is an active field nowadays and you should have as many possibilities in front of you when choosing your path. If you end up working in contact geometry graph theory probably won't help you a whole lot.

-
See the abstract to mathunion.org/ICM/ICM1986.1/Main/icm1986.1.0531.0539.ocr.pdf –  Baby Dragon Apr 26 '13 at 21:52

Mathematics is not so neatly divided into different subjects as it might seem right now. It is some kind of vast mountain, and most of it is obscured by clouds and very hard to see. It is valuable to try to look at the mountain from many different perspectives; in doing so you might see some part of the mountain you couldn't see otherwise, and that helps you better understand the mountain as a whole (which is valuable even if you currently think you are only interested in one small part of the mountain). Graph theory is one of those perspectives.

More specifically, here are some interesting connections I've learned about between graph theory and other fields of mathematics over the years.

• Graphs can be used to analyze decompositions of tensor products of representations in representation theory. See, for example, this blog post. This is related to a beautiful picture called the McKay correspondence; see, for example, this blog post. (There are some more sophisticated aspects of the McKay correspondence involving algebraic geometry I don't touch on in that post, though.)

• Graphs can be used as a toy model for Riemannian manifolds. For example, like a Riemannian manifold, they have a Laplacian. This lets you write down various analogues of differential equations on a graph, such as the heat equation and the wave equation. In this blog post I describe the Schrödinger equation on a finite graph as a toy model of quantum mechanics.

• Graphs can also be used as a toy model for algebraic curves. For example, like an algebraic curve, they have a notion of divisor and divisor class group. See, for example, this paper.

• Graphs can also be used as a toy model for number fields. For example, like (the ring of integers of) a number field, they have a notion of prime and zeta function, and there is even an analogue of the Riemann hypothesis in this setting. See, for example, this book.

But there is something to be said for learning about graphs for their own sake.

-