Combinatorics, Probability and Algorithms

combinatorics imageThe main research interests of our group lie in Combinatorics, the study of Random Discrete Structures and the analysis of Randomized Algorithms.

Combinatorial structures of particular interest are graphs and hypergraphs. Indeed, large graphs underpin much of modern society and science, and can be used to model networks in biology, sociology or computer science. These models give rise to a variety of challenging computational problems. The probabilistic perspective arises both as an invaluable method of proof as well as through the analysis of typical properties of combinatorial objects.

For more information see the Combinatorics, Probability and Algorithms in Birmingham page.

The research interests of the members of the group are given below.

Professor Daniela Kühn

Mason Chair of Mathematics

Daniela's research interests lie in Extremal and Probabilistic Combinatorics, in particular in Extremal Graph Theory, hypergraphs and random structures.

Recently she used probabilistic methods to solve several problems on Hamilton cycles in graphs and digraphs as well as generalised matching problems.

Profile

Professor Deryk Osthus 

Professor in Graph Theory

The main research area of Deryk Osthus is Combinatorics. He currently works on random graphs, randomised algorithms, Ramsey theory and extremal graph theory. The problems studied are often computationally intractable.

So a successful approach has been to find sufficient conditions which ensure some desired structure or property. He has proved numerous results of this kind for Hamilton cycles and other spanning substructures.

Profile

Dr Johannes Carmesin

Birmingham Fellow

Profile

Dr Nikolaos Fountoulakis 

Reader

Nikolaos' research interests are mainly related to the area of random discrete structures, the concept of pseudorandomness and its applications to extremal combinatorics as well as algorithms for information flow on networks.

The current focus of his research is on the analysis of graph-theoretic models for real-world networks. From this perspective, his current research has to do with random geometric graphs on spaces of negative curvature, exploring them as a candidate model for social networks.

Profile

Dr Allan Lo

Birmingham Fellow

Allan’s research interests lie in extremal and probabilistic graph theory. A typical problem in this field is to determine the necessary condition for the existence of a fixed spanning subgraph (e.g. Hamilton cycle) in a graph, edge-coloured graph, orientated graph or hypergraph.

The current focus of his research is on graph decompositions.  For example (jointly with B. Csaba, D. Kuhn, D. Osthus and A. Treglown), he recently proved the 1-factorisation conjecture and Hamilton decomposition conjecture for large graphs.

Profile

Dr Richard Montgomery

Birmingham Fellow

Dr Richard Montgomery is a Birmingham Fellow, whose research interests lie primarily in Probabilistic and Extremal Combinatorics.

Profile

Dr Richard Mycroft

Senior Lecturer

Richard's research interests lie in the field of Extremal Graph Theory. A significant area of research in this field is to determine the existence of a fixed large or spanning subgraph within a graph, directed graph or hypergraph.

For example, Richard's recent work includes the use of a randomised embedding algorithm to prove Sumner's Universal Tournament Conjecture for large tournaments. This states (loosely) that any sufficiently large tournament contains any tree on roughly half the number of vertices.

More recently his focus has been on finding perfect matchings and packing's in hypergraphs.

Profile

Dr Guillem Perarnau

Lecturer

Guillem's main research interest is in the use of probabilistic techniques to study both deterministic and typical properties of sparse combinatorial objects. For instance, he has been recently working on the analysis of non classical random graphs models.

Profile

Dr Henning Sulzbach

Lecturer

Henning is mainly interested in probability theory and its applications to the analysis of algorithms and random graphs. The probabilistic analysis of algorithms aims at obtaining a better understanding of average and worst-case complexity of important algorithms in computer science. In the analysis of random graphs, the main objective is the description of the geometry of networks of very large size. Applications include social networks, data structures and phylogenetic trees. 

Profile

Dr Eoin Long

Lecturer

Eoin's research interests encompass a wide array, including Extremal combinatorics, Graph Theory, Ramsey theory, Probabilistic methods in combinatorics and High-dimensional phenomena.

Profile

Dr Andrew Treglown

Senior Lecturer

Andrew’s primary research interests lie in extremal and probabilistic graph theory as well as in Ramsey theory.

Recently Andrew has been working on problems concerning graph decompositions including the 1-factorisation conjecture. With his coauthors, he solved a classical Ramsey problem of Goodman concerning the number of monochromatic triangles in three-coloured graphs. Andrew has also worked on a number of embedding problems in the directed graph and hypergraph setting.

Profile