Lecture: Graph Theory: From Puzzles to a New Paradigm

László Lovász

Graph theory had a very modest beginning. In 1736, Euler solved the puzzle of the Königsberg bridges, and for a long time, it was considered to be “recreational mathematics”. This view was still rather common when I was a student, although due to activities of the great Paul Erdős and others, not only were the results getting more and more deep and difficult, but also finding more and more connections with other branches of mathematics and the sciences.

In this talk, I’ll recall how working on graph-theoretic problems took me to computer science, to optimization and even to physics. Nowadays, a new paradigm of science is emerging: Network theory is the language needed to describe complex structures from the internet to the ecology to the brain. Graph theory can be considered the mathematical foundation of network science, and its importance cannot be questioned any more. True, graph theory does not have the long-established and well-understood structure of analysis (which had a head start of 2-3 centuries), but this makes its study even more challenging and rewarding.

---