Combinatorics and Graph Theory
Questions in combinatorics can be traced back to the very early days of mathematics. It mainly involves problems regarding finite, but nevertheless large, objects including (hyper)graphs, permutations, Latin squares and partitions of sets.
Many combinatorial questions have a common feature: They are very easy to state, even to non-professional mathematicians, but they resist any attempt to crack them for decades. One of those questions, which is solved by now, is the problem whether any map can be coloured with four colours in such a way that any country receives one of these four colours and each pair of countries that share a common border receive different colours (the Four Colour Theorem).
Many developments in the past decades come with the exploitation of tools from other areas such as probability theory, analysis, number theory, ergodic theory and algebra.
Here in Heidelberg, we mostly deal with graphs and hypergraphs. Hypergraphs are simply subsets of the powerset of a finite set. The finite set is called its vertex set whereas the elements of the subset are called edges. In most cases we consider uniform hypergraphs, that is, each edge contains the same number of elements. If all edges have size 2, then the hypergraph is called a graph. The above mentioned Four Colour Theorem can be reformulated as a partition question of the vertex set of a particular class of graphs (planar graphs), where we aim to partition the vertex set into four classes such that no edge is inside a vertex class.
We often use randomized approaches in our proofs. To this end, we design a random process that evolves over time thereby constructing a combinatorial object and we try to analyse the typical outcome of such a random process. In the past this approach proved to be extremely successful and is called the probabilistic method.
One core expertise in our research group concerns questions that deal with sufficient conditions that allow us to find particularly nice subgraphs in a large host graphs and when a large graph admits a decomposition into small predefined graphs.