Prof. Dmitry Feichtner-Kozlov

Diese Seite existiert nur auf Englisch!

Discrete Mathematics

Discrete Mathematics is a branch of modern mathematics which distinguishes itself from the more classical branches in several important respects. Probably the most characteristic feature, "the trademark" of Discrete Mathematics is to study mathematical concepts in a constructive way. The classical question Does there exist an object with property X? gets transformed into How can we construct an object with property X?

Discrete Mathematics is closely related to Theoretical Computer Science, playing a major role in the design of fast algorithms, as well as in complexity analysis.

Here is one classical connection. When trying to construct an effective algorithm for some problem, one is usually faced with the necessity of choosing an appropriate data structure. This is a much more sophisticated task then appears at the first sight. Even if the input data is given in some standard way, such as an array, it might be highly beneficial to reorganize this data, this is often called preprocessing, according to the factual contents of the array, so as to produce a data structure, on which different operations (queries, swaps, data addition, etc), which our algorithm uses, can be performed effectively.

The resulting structures can be very different. Ranging from simple ones, such as lists sorted according to some attribute, to more sophisticated ones, such as various dynamically balanced trees. The unifying feature of these discrete data structures is that they are chosen because of certain properties which help the algorithm to run effectively.

This is where Discrete Mathematics comes in.

On the one hand, Discrete Mathematics studies properties of classical discrete structures, such as graphs, trying to discover those properties which are useful for various algorithmic tasks.

The Berliner Zeitung has published an article about combinatorics and Dmitry Feichtner-Kozlov.
Dmitry Feichtner-Kozlov, assistant professor at the institute of
theoretical computer science, has recently been awarded the European
Prize in Combinatorics. »»

On the other hand, Discrete Mathematics tries to construct more sophisticated structures, which would satisfy a list of prescribed properties ordered by the prospective algorithm writer. There are many areas, for example Discrete Geometry, where the choice of underlying data structures is highly non-unique, and is a subject of intensive research.

The other face of Discrete Mathematics is its relation with classical branches of mathematics. My own research lies in this direction, especially investigating relations to algebraic topology.

On a philosophical level, discrete structures occurring everywhere in mathematics, provide a high-level abstraction for many mathematical concepts. Many connections between seemingly different mathematical facts become first apparent in this discrete framework.

Discrete Mathematicians (also called combinatorialists) often ask questions like Is this a combinatorial invariant? much like algebraists want to know whether the observed geometric properties of the space can be derived from the associated algebraic model alone, or analysts wonder whether the conjectured phenomenon depend on the differential structure only.

One distinguishing feature of Discrete Mathematics is that the problems often have elementary, even playful formulations. Sometimes the reasons for this are historical, sometimes this is meant ironically, to underline the unsolvability of so many fundamental problems.

While often only elementary concepts are required to formulate questions in Discrete Mathematics, the same cannot be said about the methods. Modern Discrete Mathematics employs highly sophisticated methods from virtually all parts of mathematics. This "language discrepancy" is somewhat similar to number theory, where many questions, such as Fermat's Last Theorem, can be formulated using elementary arithmetics only, whereas the state-of-the-art language used for attacking the problems involves highly advanced analytic and algebro-geometric concepts.

As an example, in one of my latest research projects, we were considering a classical problem of graph colorings. Given a graph, one is asked to find a minimal number of colors to color the vertices so that no edge receives the same color on both ends; the so-called chromatic number. This is a classical combinatorial question, having high computational complexity, and appearing in very many applications.

We discovered that such mathematical concepts as Stiefel-Whitney characteristic classes are closely related to the chromatic number, and in fact are useful for providing lower bounds which are computable in polynomial time! Once on this track, one is then forced to use a great deal of algebraic-topological machinery, such as computing with spectral sequences.