Random graphs
The main problem considered but unsolved in the early days of work on random regular graphs (starting around 1978) was the question of hamiltonicity. With Bob Robinson [1], I showed that large random d-regular graphs are almost always Hamiltonian (for d at least 3). The method we used was actually to show that under certain conditions, two sequences of probability spaces share 'asymptotically almost sure' properties (in which they are called contiguous). It led to many results stating that random d-regular graphs are contiguous to random regular graphs built in other ways, such as by two random Hamilton cycles (joint result with Jeong Han Kim [2]).
The determination of the threshold at which a random graph develops a k-core (with Boris Pittel and Joel Spencer [3]) has a number of applications and has been rederived by many other authors recently.
Random graphs evolve in a well studied fashion, and when the average degree is just greater than 1, there develops a giant component. Various properties of this giant component have been studied recently. In particular I have looked at mixing time of the random walk (with Benjamini and Kozma [4] -- this uses some knowledge of the 2-core and tricks picked up when using the d.e. method described below) and am studying diameter (with Oliver Riordan) and the length of the longest cycle (lower bounds with Jeong Han Kim, upper bounds with my student Graeme Kemkes[5]).
Cores also play a strong role in the topic 'Asymptotic enumeration of graphs' described below.
Many other topics are of interest. Of all my papers, the one whose title seems to be the favourite of some people is 'Birth Control for Giants', with Joel Spencer, where we consider the time of birth of the giant component of the random graph in a so-called Achlioptas process. The question was how much the birth can be delayed by influencing the choices in the process.
[1] R.W. Robinson and N.C. Wormald,
Almost all regular graphs are hamiltonian,
Random Structures and Algorithms
5 (1994), 363-374.
[2] J.H. Kim and N.C. Wormald, Random matchings which induce Hamilton
cycles, and hamiltonian decompositions of random regular graphs, J.
Combinatorial Theory, Series B 81 (2001), 20-44.
[3] B. Pittel, J. Spencer and N.C. Wormald,
Sudden emergence of a giant $k$-core in a random graph,
J. Combinatorial Theory, Series B
67 (1996), 111-151.
[4] I. Benjamini, G. Kozma and N. Wormald,
The mixing time of the giant component of a random graph,
http://arxiv.org/abs/math/0610459.
[5] G. Kemkes and N. Wormald,
An improved upper bound on the length of the longest cycle of a post-critical random graph,
SIAM J. Discrete Math.
27 (2013), 342-362.
(pdf)
Abstract
Random structures and algorithms
See the section on Algorithms in my Recent
publications.
Regular graphs of large girth
I discovered with Joe Lauer [1], who was an undergraduate student at the time, that some of the greedy algorithms I am used to analysing on random regular graphs can also analysed very precisely when they are applied to any regular graph of very large girth. We studied a simple algorithm for finding large independent sets, and improved most of the best known lower bounds for this. Work with my student Carlos Hoppen[2,3] is extending this to a number of different algorithms that significantly improve the bounds known for many different structures in regular graphs of large girth. The method is strongly related to the work I have done applying the differential equation method to random regular graphs.
[1] J. Lauer and N. Wormald,
Large independent sets in regular graphs of large girth,
J. Combinatorial Theory, Series B
97 (2007), 999-1009. (pdf)
Abstract
[2] C. Hoppen and N. Wormald,
Induced forests in regular graphs with large girth,
Combinatorics, Probability and Computing
17 (2008), 389-410.
(Math arXiv link)
[3] C. Hoppen and N. Wormald,
Local algorithms, regular graphs of large girth, and random regular graphs
(Math Arxiv link)
Asymptotic enumeration of graphs
Some old but interesting enumeration problems have been solved recently. Counting (labelled) graphs tends to be easy, but finding (an asymptotic formula) the number of connected graphs with given edge density seems to defy all elementary techniques. The solutions use random structures and the properties of random graphs. Random graphs with given degree sequence enter the picture as well. Topics dealt with include connected graphs with given numbers of vertices and edges [1], 2-connected graphs with given number of edges [2] which formed part of Cris Sato's PhD thesis, strongly connected directed graphs with given number of vertices and arcs [3], and connected hypergraphs with a given number of vertices and hyperedges (current work with Cris Sato and Huseyin Acan).
[1] B. Pittel and N.C. Wormald, Counting connected
graphs inside-out,
J. Combinatorial Theory, Series B
93 (2005), 127-172.
(pdf)
Abstract
[2] G.Kemkes, C.M. Sato and N. Wormald,
Asymptotic enumeration of sparse 2-connected graphs,
Random Structures and Algorithms
43 (2013), 354-376.
(pdf)
Abstract
[3] X. Perez-Gimenez and N. Wormald,
Asymptotic enumeration of strongly connected digraphs by vertices and edges,
Random Structures and Algorithms
43 (2013), 80-114.
(pdf)
Abstract
Differential equation method
This method gives a theoretical justification of the intuitive idea that a system of random steps will follow the expected trends with high probability. At a time when there were few rigorous applications of this idea to discrete structures, and only using continuous random variables, I introduced a general argument that uses only the discrete variables concerned (and supermartingales) [1,2]. This lends itself to versatile adaptation where discrete structures are concerned. One of the main uses I have put it to are deriving bounds on properties of random regular graphs, such as the size of independent sets, or dominating sets (with Billy Duckworth [3]).
[1] N.C. Wormald,
Differential equations for random processes and random graphs,
Annals of Applied Probability
5 (1995), 1217-1235.
[2] N.C. Wormald, The differential equation method for random
graph processes and greedy algorithms, in Lectures on Approximation
and Randomized Algorithms (M. Karonski and H.J. Proemel, eds), pp. 73-155.
PWN, Warsaw, 1999.
[3] W. Duckworth and N.C. Wormald, On the independent domination
number of random regular graphs, Combinatorics, Probability
and Computing 15 (2006), 513-522.
Enumeration of convex polyhedra
This is a problem which Euler showed some interest in, and even early in the nineteenth century Steinitz asked essentially for a formula for the number of (inequivalent) convex polyhedra with n faces. I obtained a system of recursive formulae 25 years ago that gave the answer in time polynomial in n, but it was too horrible to write up. Recent work with Bob Robinson has shown that these numbers can be obtained from a small set of simple recurrences (the recurrences have a fixed number of terms, but the number of terms may be quite large).