Discrete mathematics has its origins at the intersection of mathematics and computer science, but in recent decades, it has been established as an independent field of study. Its models, methods, tools, and algorithms are at the core of key application fields such as transportation, logistics, telecommunications, bioinformatics, and image processing, to mention just a few.

Modern methods of discrete mathematics are remarkably diverse and flexible: Their spectrum includes algorithmic, randomized, probabilistic, approximative, geometric, topological, algebraic, and optimization methods. The combination and interaction of such tools has enormously increased the power and the range of combinatorial reasoning in recent years, especially for applications in computer science, optimization, and operations research.

Over the past twenty years, Berlin has developed into an internationally visible and acclaimed place for graduate education in discrete mathematics and optimization. This is due not only to the activities of individual faculty members and groups, but even more so to the joint activities of the research groups in discrete mathematics and optimization at FU, HU, TU, and ZIB. These include the RTGs Algorithmic Discrete Mathematics (1990–1998) and Combinatorics, Geometry and Computation (2000–2005), with their colloquia, block courses, and summer schools.

The RTG Methods for Discrete Structures (2006–) is a certified unit of BMS and encompases the research activities in the fields of discrete mathematics and combinatorial optimization. Its strong and tightly connected research groups are making substantial contributions to almost all aspects of these fields. They have experience both in joint work as well as in joint graduate education, and thus provide a first-class environment for graduate training in discrete mathematics.

In the following, we give some prominent examples of research areas in discrete mathematics and combinatorial optimization that we are working on. Naturally, these different areas are strongly interrelated, and many interesting research questions have connections to several of these areas.

Graphs are fundamental building blocks in many areas of discrete mathematics and theoretical computer science; important and interesting concepts include planarity, minor theory, orientation, extremal properties, partial orders and network optimization (Felsner, Grötschel, Möhring). Within the past years, also due to several new faculty members, special emphasis has been laid on the area of approximation and online algorithms for hard problems in discrete optimization (Albers, Grohe, Skutella). In combinatorial optimization, substantial effort is being put into the development of mathematical tools and algorithms (such as network flow algorithms and integer programming techniques) to the point where their impact can be seen on genuine industrial applications. Much of the Berlin effort in this direction is based at ZIB (Grötschel, Borndörfer) and in Application Area B Networks of MATHEON.

Discrete and combinatorial geometry is a broad field in which topological and algebraic methods have found striking applications to combinatorial problems (Ziegler). The more computer-science oriented field of computational geometry is particularly concerned with the complexity of algorithms for geometric problems (Alt, Rote). Extremal and probabilistic combinatorics are two thriving branches in current combinatorial research; they are strongly interrelated and influence each other in many ways (Szabó).