Nick Wormald


Professor
Department of Mathematical Sciences
Monash University VIC 3800
Australia

Office: Room 455, 9 Rainforest Walk.
Email: nicholas.wormald@monash.edu

Research

  • Combinatorics
  • Random Graphs
  • Graph Theory
  • Enumeration of Graphs, Maps and Combinatorial Structures
  • Probabilistic Combinatorics
  • Combinatorial and Graph Algorithms
  • Shortest Networks and Steiner Trees
  • Underground Mine Optimisation

    • Recent publications.

    Full list of publications updated in September 2017.

    (Some recent research topics are listed below.)

    Videos

    For everybody - what it's like to be a mathematician: a 2-minute description.

    For the scientist - my research in 12 minutes: a presentation to an audience of scientists at the Australian Academy of Science.

    For the mathematician - a more detailed description of some recent research: invited talk in the Combinatorics session at the 2018 ICM in Rio de Janeiro.

    Editorial

    Member of the Editorial Boards of:

  • Journal of Combinatorial Theory, Series B
  • Australasian Journal of Combinatorics
  • Electronic Journal of Combinatorics
  • Journal of Graph Theory
  • Random Structures and Algorithms

    • Software

    Do you want to generate graphs with given degrees uniformly at random? Here is C code for the algorithms INC-GEN and INC-REG in A. Arman, P. Gao and N. Wormald, Fast uniform generation of random graphs with given degree sequences, 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) 1, 1371-1379 (2019).

    Some recent research topics

    Note: many of the papers referred to below are downloadable from here.


    Properties of random graphs

    Many results in graph theory concern Hamilton cycles, i.e. cycles that pass through all vertices of the graph (without repeats). 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. One paper that has attracted attention 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.

    Consider the distribution of vertex degrees of a random graph. Each vertex degree by itself is distributed as a binomial random variable. What about the joint distribution of vertex degrees? Recently, Anita Liebenau and I proved some old conjectures on asymptotic formulae (see below) that imply that the vertex degrees in a random graph act very much like independent binomials. This allows us to study the degree sequence of a random graph by studying sequences of independent binomials.

    [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


    Asymptotic enumeration of graphs

    How many regular graphs are there on n vertices? How many graphs with vertices of given degrees that are not necessarily all the same? A new technique for getting useful approximate (asymptotic) formulae has just been worked out [1]. This solved several very old problems and conjectures. Answers to these questions also tell us about the typical degree sequences of a random graph. (See the random graphs section above.)

    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 found recently use random structures and the properties of random graphs. Topics dealt with include connected graphs with given numbers of vertices and edges [2], 2-connected graphs with given number of edges [3] which formed part of Cris Sato's PhD thesis, strongly connected directed graphs with given number of vertices and arcs [4], and connected hypergraphs with a given number of vertices and hyperedges (current work with Cris Sato and Huseyin Acan).

    [1] A. Liebenau and N. Wormald, Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph,  arXiv preprint 2017 (Abstract and pdf)

    [2] B. Pittel and N.C. Wormald, Counting connected graphs inside-out,  J. Combinatorial Theory, Series B 93 (2005), 127-172. (pdf) Abstract

    [3] 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

    [4] 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

    Random structures and algorithms

    See the section on Algorithms in my Recent publications.


    Generating random graphs with given degrees

    To sample uniformly at random from a set of objects is sometimes difficult. Recently I introduced with Jane Gao a new approach to generating random graphs with given degrees. These can be used for various purposes, including establishing null hypotheses in biological questions. The main idea was introduced in [1] and further work continues in various directions.

    [1] P. Gao and N. Wormald, Uniform generation of random regular graphs, Proceedings of 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) (2015) pp. 1218-1230. See also SIAM J. Comput. 46 (2017), 1395-1427.


    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 PhD student Carlos Hoppen [2,3] recently extended 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, Combinatorica (to appear). (Math Arxiv link.) See also Properties of regular graphs with large girth via local algorithms, J. Combinatorial Theory, Series B, 121 (2016), 367-397.


    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).

    Last updated: 9th August 2020