Invited Presentation: Discrete Mathematics and Theoretical Computer Science

Martin Grötschel
Konrad-Zuse-Zentrum and TU Berlin, Berlin, Germany

The meaning of the term Discrete Mathematics (DM) has evolved over the last decades. Today it includes (roughly) classical combinatorics, graph theory, combinatorial optimization, integer programming, matroid theory, coding theory, and even some branches of geometry, algebra, and number theory. Discrete Mathematics overlaps significantly with Theoretical Computer Science (TCS), in particular in the theory of algorithms. Driven by the explosive growth of computing power and by numerous applications, DM & TCS have experienced tremendous progress in the last 50 years - both in theory and in their use in practice. There is no way to cover all the areas and all success stories. I will focus on a few highlights (of my choice) and will try to show the advances that have been achieved along these examples. Success in theory is typically marked by the proof of important theorems. The max flow-min cut theorem, the characterization of totally unimodular matrices, the matroid intersection theorem, the 4-color theorem, and the perfect graph theorem are five of many examples of a rich harvest of this kind that I will mention. Progress is often fueled by new notions and theories providing suitable tools and concepts for the understanding of unexplained phenomena. Prime examples here are the concept of NP- and other types of completeness, general complexity theory, and the theory of random graphs, all developed in the last 50 years. Our daily life is full of (usually unnoticed) contacts with DM & TCS. Whether we ride a city bus, fly in an airplane, find a route with a car navigation system, order a book, use a phone, or withdraw money from an ATM, DM & TCS are involved in some fundamental way. I will present some breakthroughs in the algorithmic solution technology focussing on large-scale real-world examples of this kind.