Combinatorics, especially Extremal and Probabilistic Graph Theory
My research interests lie in Graph Theory, Probabilistic Methods and Randomized Algorithms. Recently I have focused on sufficient conditions for Hamilton cycles in directed graphs, i.e. cycles which contain all the vertices of the directed graph. It is unlikely that there is a good characterization of all (directed) graphs containing a Hamilton cycle since the corresponding decision problem is NP-complete. So it is natural to ask for sufficient conditions for the existence of a Hamilton cycle.
The most famous such conditions is Dirac's theorem that every graph in which every vertex is joined by an edge to at least half of the vertices has a Hamilton cycle. An analogue of Dirac's theorem for directed graphs was proved by Ghouila-Houri. Recently we proved an analogue of Dirac's theorem for oriented graphs, i.e. for directed graphs without cycles of length 2. Dirac's theorem was strengthened by Posa and Chvatal who gave conditions on the degree sequence of a graph which still guarantee Hamiltonicity. We have also recently obtained approximate versions of Posa's and of Chvatal's theorem for directed graphs. I have collaborated with D. Christofides, P. Keevash, L. Kelly, D. Osthus and A. Treglown on these questions.