Abstract of the Commemorative lecture
A Fledgeling Subject Bridging Classical Theory and New Applications
I was introduced to my main research topic of graph theory in high school. I was lucky enough to be enrolled in a new specialized high school class for mathematics. Not only did I meet many outstanding students there (including my wife), but the famous mathematician Paul Erdős visited the school several times. He gave the students unsolved problems, one or two of which I could solve; so started my lifelong commitment to graph theory and to mathematical research. In those days, graph theory was still quite isolated from “mainstream” mathematics, and later I was often advised by older mathematicians to do something more serious instead. But for me, the novelty of the subject and its potential applications were fascinating.
In the last years of my studies, I got interested in the strong connection between operations research and graph theory. I solved a problem about perfect graphs, and the method of solution turned out to have interesting consequences in integer programming and through this, to polyhedra. I have found repeatedly that this connection between graph theory, optimization, and geometry is most fruitful.
Shortly after this, I learned about the new theory of algorithmic complexity, which had a lot of consequences in graph theory. This allowed me to be a witness (and a bit, a participant) of the fascinating co-development of the theory of computing and its mathematical basis, discrete mathematics (which includes graph theory).
Graph theory also has connections in the opposite direction, to classical mathematics, and I got fascinated with the question of applying such methods to solve graph-theoretical problems. Algebra, topology, geometry and probability theory are among those areas which can be applied in graph theory in interesting ways.
More recently, I got interested in the theory of very large networks (like the internet). This gives another new twist to graph theory, and further areas of classical mathematics turn out to be needed here. I have to re-learn areas that I last met when I was a student, I enjoy this enormously.
