Our research interests lie in a range of different topics in discrete mathematics, with connections to many other areas such as algebra, coding theory, logic, number theory, optimization, probability theory, and theoretical computer science.
A graph is an abstract mathematical structure which consists of vertices (sometimes called nodes) and edges, where every edge connects two vertices. They can be used to model all kinds of real-world networks and are therefore one of the key structures studied in theoretical computer science and optimization.
We study abstract structural properties of such graphs and how different graph parameters relate to each other. There are many unsolved problems in graph theory. Perhaps the most significant one is Hadwiger's conjecture from 1943. The chromatic number of a graph is the least possible number of colours such that the graph can be coloured with neighbouring vertices always receiving distinct colours. A complete minor is a substructure of a graph consisting of disjoint parts which themselves induce connected subgraphs, and such that between any two parts there is at least one edge in the graph. Hadwiger conjectured that if a graph needs a certain number of colours to be coloured, then it must contain a complete minor with that same number of parts. The problem is often considered as one of the deepest unsolved mysteries in graph theory. It contains the famous four colour theorem as a special case.
In extremal combinatorics, the basic question is how dense a certain structure can be under restrictions such as forbidding certain substructures. For instance, how many edges can a graph have if it does not contain a triangle? This is answered by Mantel's theorem. However, if the triangle is replaced by a cycle of length eight, the problem is still wide open.
One of the most important challenges in this area is to solve a problem of Turán that the maximal density of a 3-uniform hypergraph without a tetrahedron (the complete 3-uniform hypergraph on 4 vertices) is 5/9. But there are many other problems that are similarly hard. Such questions can be asked not only for graphs or hypergraphs, but also for other structures, like sets of numbers avoiding certain patterns like arithmetic progressions, or geometric objects with certain restrictions. The study of such problems has benefited from tools from many other areas, and it has also brought forth a lot of novel methods which in turn have shaped these areas for decades, for instance, Szemerédi's regularity method. Often, probabilistic methods are used, both for showing existence of extremal structures and for finding the forbidden substructures if the density is too large. The theory of graph limits uses analytic approaches to give compact descriptions of the asymptotic nature of extremal structures. The flag algebra method is formulated in the language of model theory to make such problems amenable to computer-assisted proofs. Many explicit constructions of extremal structures are based on algebraic methods. Topological methods and tools from optimization have also become indispensable in this field.
One of the most intriguing methods used in combinatorics is the probabilistic method, pioneered by Paul Erdős. The stunning observation is that, in order to show existence of some object with certain properties, it suffices to construct a probability space over all admissible objects in which a randomly chosen object satisfies the desired properties with positive probability. This idea has revolutionized research in combinatorics. The usage of this method ranges from quite simple instances where an object is chosen uniformly at random from some set to more advances techniques like random processes where the object is constructed in many random steps, and tools from probability theory like martingale inequalities are used to analyze such processes. However, probabilistic combinatorics not only entails the usage of probabilistic methods to prove purely combinatorial results, but also encompasses the study of discrete random structures like random graphs for their own sake, which often exhibit fascinating threshold phenomena.
Complete chaos is impossible: that's the core principle of Ramsey theory, an area named after Frank Plumpton Ramsey, who was a British mathematician, philosopher and economist. Roughly speaking, it is the qualitative or quantitative study of the phenomenon that every large enough structure, no matter how chaotic it may be, must contain some very homogenous substructure. For instance, in graph-theoretic language, it asks for the function r(s,t) which, for two given values s and t, is defined as the minimum order such that every graph of that order either contains a clique (which is a complete subgraph) of order s, or an independent set (which is an empty subgraph) of order t. In recent years, there have been some exciting breakthroughs on questions that seemed almost impossible before.
