Graph Theory Exploration

Question

I'm a student currently taking a Graph Theory course. I'm very much enjoying it so far, and am looking to do some learning on my own. Are there any extremal topics (i.e. topics or concepts which a class may not touch on but may be interesting, perhaps applications of graph theory concepts to other areas of math, perhaps calculus) that you guys/gals can think of?

Thanks.

Answer 1

Misha Lavrov said the words of a true graph theorist. When we see graphs anywhere where it is possible, we are going towards graph theory Zen, allowing us to see the base graph of the world, as at the following picture:

Indeed, according to a modern theory in quantum physics, namely, the theory of loop quantum gravity, at the fundamental level the universe looks like a huge graph (You can see relevant pictures in this article by Lee Smolin. This time something happened with the codepage, but, anyway, the paper was in Russian).

A part of truth in these jokes is that the bigger is your knowledge of mathematics, the more applications of graph theory you can find. I can illustrate this by the following list of applications in MSE threads in which I participated:

• Finite Ramsey’s Theorem in number theory.
• Finite Ramsey’s Theorem in combinatorial geometry.
• Finite Ramsey’s Theorem in combinatorial geometry 2.
• Infinite Ramsey’s Theorem in real analysis.
• Four Color Theorem in general topology.
• Cycles in additive number theory. Here I remark that Taras Banakh used binary trees to show that any $S$ finite non-empty subset of an abelian group such that $ S\subset S+S$ has two non-empty subsets $A$ and $B$ such that $\sum A+\sum B=0$. I’ll provide a link to the proof when we put this paper to arXiv.
• Euler's formula in combinatorial geometry which came from a computer science problem from a very fundamental level.
• Turán's and Kővári–Sós–Turán’s theorems in a similar topic,
• Depth-first search in a table-turning puzzle,
• Domatic number in a stage magic.

At last, although the theory of loop quantum gravity it arguable, this problem by Davide Venturelli is a part of a research objective connected to quantum computing.

Moreover, recently at MathOverflow Mario Krenn asked “a purely graph-theoretic question motivated by quantum mechanics” (and a special case of the questions asked in only a two-week old arXiv paper "Questions on the Structure of Perfect Matchings inspired by Quantum Physics” by Mario Krenn, Xuemei Gu and Daniel Soltész). I allow myself to quote here fragments from the beginning and the conclusion of the paper:

A bridge between quantum physics and graph theory has been uncovered recently [1, 2, 3]. [These are fresh papers, among others, of the first two authors and Anton Zeilinger, a famous specialist in quantum physics. AR] It allows to translate questions from quantum physics – in particular about photonic quantum physical experiments – into a purely graph theoretical language. The question can then be analysed using tools from graph theory and the results can be translated back and interpreted in terms of quantum physics. The purpose of this manuscript is to collect and formulate a large class of questions that concern the generation of pure quantum states with photons with modern technology. This will hopefully allow and motivate experts in the field to think about these issues. ...

Every progress in any of these purely graph theoretical questions can be immediately translated to new understandings in quantum physics. Apart from the intrinsic beauty of answering purely mathematical questions, we hope that the link to natural science gives additional motivation for having a deeper look on the questions raised above.