Professor

Department of Mathematical Sciences

Monash University VIC 3800

Australia

Office: Room 455, 9 Rainforest Walk.

Email: nicholas.wormald@monash.edu

Full list of publications updated in September 2017.

(Some recent research topics are listed below.)

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.

Member of the Editorial Boards of:

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

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

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

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

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

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

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

Last updated: 9th August 2020