Source author record

Nicholas Wormald

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.PR Data Structures and Algorithms Discrete Mathematics

Catalog footprint

Research overview

12works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Fast uniform generation of random graphs with given degree sequences

In this paper we provide an algorithm that generates a graph with given degree sequence uniformly at random. Provided that $Δ^4=O(m)$ , where $Δ$ is the maximal degree and $m$ is the number of edges,the algorithm runs in expected time $O(m)$ . Our algorithm significantly improves the previously most efficient uniform sampler, which runs in expected time $O(m^2Δ^2)$ for the same family of degree sequences. Our method uses a novel ingredient which progressively relaxes restrictions on an object being generated uniformly at random, and we use this to give fast algorithms for uniform sampling of graphs with other degree sequences as well. Using the same method, we also obtain algorithms with expected run time which is (i) linear for power-law degree sequences in cases where the previous best was $O(n^{4.081})$ , and (ii) $O(nd+d^4)$ for $d$ -regular graphs when $d=o(\sqrt n)$ , where the previous best was $O(nd^3)$ .

preprint2021arXiv

Uniform generation of random regular graphs

We develop a new approach for uniform generation of combinatorial objects, and apply it to derive a uniform sampler REG for d-regular graphs. REG can be implemented such that each graph is generated in expected time O(nd^3), provided that d=o(n^{1/2}). Our result significantly improves the previously best uniform sampler, which works efficiently only when d=O(n^{1/3}), with essentially the same running time for the same d. We also give a linear-time approximate sampler REG*, which generates a random d-regular graph whose distribution differs from the uniform by o(1) in total variation distance, when d=o(n^{1/2}).

preprint2016arXiv

Enumeration of graphs with a heavy-tailed degree sequence

In this paper, we asymptotically enumerate graphs with a given degree sequence d=(d_1,...,d_n) satisfying restrictions designed to permit heavy-tailed sequences in the sparse case (i.e. where the average degree is rather small). Our general result requires upper bounds on functions of M_k= \sum_{i=1}^n [d_i]_k for a few small integers k\ge 1. Note that M_1 is simply the total degree of the graphs. As special cases, we asymptotically enumerate graphs with (i) degree sequences satisfying M_2=o(M_1^{ 9/8}); (ii) degree sequences following a power law with parameter gamma>5/2; (iii) power-law degree sequences that mimic independent power-law "degrees" with parameter gamma>1+\sqrt{3}\approx 2.732; (iv) degree sequences following a certain "long-tailed" power law; (v) certain bi-valued sequences. A previous result on sparse graphs by McKay and the second author applies to a wide range of degree sequences but requires Delta =o(M_1^{1/3}), where Delta is the maximum degree. Our new result applies in some cases when Delta is only barely o(M_1^ {3/5}). Case (i) above generalises a result of Janson which requires M_2=O(M_1) (and hence M_1=O(n) and Delta=O(n^{1/2})). Cases (ii) and (iii) provide the first asymptotic enumeration results applicable to degree sequences of real-world networks following a power law, for which it has been empirically observed that 2<gamma<3.

preprint2016arXiv

The mixing time of the giant component of a random graph

We show that the total variation mixing time of the simple random walk on the giant component of supercritical Erdos-Renyi graphs is log^2 n. This statement was only recently proved, independently, by Fountoulakis and Reed. Our proof follows from a structure result for these graphs which is interesting in its own right. We show that these graphs are "decorated expanders" - an expander glued to graphs whose size has constant expectation and exponential tail, and such that each vertex in the expander is glued to no more than a constant number of decorations.

preprint2014arXiv

Cycle factors and renewal theory

For which values of $k$ does a uniformly chosen $3$ -regular graph $G$ on $n$ vertices typically contain $n/k$ vertex-disjoint $k$ -cycles (a $k$ -cycle factor)? To date, this has been answered for $k=n$ and for $k \ll \log n$ ; the former, the Hamiltonicity problem, was finally answered in the affirmative by Robinson and Wormald in 1992, while the answer in the latter case is negative since with high probability most vertices do not lie on $k$ -cycles. Here we settle the problem completely: the threshold for a $k$ -cycle factor in $G$ as above is $κ_0 \log_2 n$ with $κ_0=[1-\frac12\log_2 3]^{-1}\approx 4.82$ . Precisely, we prove a 2-point concentration result: if $k \geq κ_0 \log_2(2n/e)$ divides $n$ then $G$ contains a $k$ -cycle factor w.h.p., whereas if $k<κ_0\log_2(2n/e)-\frac{\log^2 n}n$ then w.h.p. it does not. As a byproduct, we confirm the "Comb Conjecture," an old problem concerning the embedding of certain spanning trees in the random graph $G(n,p)$ . The proof follows the small subgraph conditioning framework, but the associated second moment analysis here is far more delicate than in any earlier use of this method and involves several novel features, among them a sharp estimate for tail probabilities in renewal processes without replacement which may be of independent interest.

preprint2014arXiv

On the degree distribution of a growing network model

In this note we make some specific observations on the distribution of the degree of a given vertex in certain model of randomly growing networks. The rule for network growth is the following. Starting with an initial graph of minimum degree at least $k$ , new vertices are added one by one. Each new vertex $v$ first chooses a random vertex $w$ to join to, where the probability of choosing $w$ is proportional to its degree. Then $k$ edges are added from $v$ to randomly chosen neighbours of $w$ .

preprint2014arXiv

The threshold for combs in random graphs

For $k\mid n$ let $Comb_{n,k}$ denote the tree consisting of an $(n/k)$ -vertex path with disjoint $k$ -vertex paths beginning at each of its vertices. An old conjecture says that for any $k=k(n)$ the threshold for the random graph $G(n,p)$ to contain $Comb_{n,k}$ is at $p\asymp \frac{\log n}n$ . Here we verify this for $k \leq C\log n$ with any fixed $C>0$ . In a companion paper, using very different methods, we treat the complementary range, proving the conjecture for $k\geq κ_0 \log n$ (with $κ_0\approx 4.82$ ).

preprint2011arXiv

Asymptotic enumeration of sparse 2-connected graphs

We determine an asymptotic formula for the number of labelled 2-connected (simple) graphs on $n$ vertices and $m$ edges, provided that $m-n\to\infty$ and $m=O(n\log n)$ as $n\to\infty$ . This is the entire range of $m$ not covered by previous results. The proof involves determining properties of the core and kernel of random graphs with minimum degree at least 2. The case of 2-edge-connectedness is treated similarly. We also obtain formulae for the number of 2-connected graphs with given degree sequence for most (`typical') sequences. Our main result solves a problem of Wright from 1983.

preprint2011arXiv

Asymptotic enumeration of strongly connected digraphs by vertices and edges

We derive an asymptotic formula for the number of strongly connected digraphs with $n$ vertices and $m$ arcs (directed edges), valid for $m-n\to\infty$ as $n\to \infty$ provided $m=O(n\log n)$ . This fills the gap between Wright's results which apply to $m=n+O(1)$ , and the long-known threshold for $m$ , above which a random digraph with $n$ vertices and $m$ arcs is likely to be strongly connected.

preprint2010arXiv

Induced subgraphs in sparse random graphs with given degree sequence

For any $S\subset [n]$ , we compute the probability that the subgraph of $\mathcal{G}_{n,d}$ induced by $S$ is a given graph $H$ on the vertex set $S$ . The result holds for any $d=o(n^{1/3})$ and is further extended to $\mathcal{G}_{\bf d}$ , the probability space of random graphs with a given degree sequence $\bf d$ .

preprint2010arXiv

Orientability thresholds for random hypergraphs

Let $h>w>0$ be two fixed integers. Let $\orH$ be a random hypergraph whose hyperedges are all of cardinality $h$ . To {\em $w$ -orient} a hyperedge, we assign exactly $w$ of its vertices positive signs with respect to the hyperedge, and the rest negative. A $(w,k)$ -orientation of $\orH$ consists of a $w$ -orientation of all hyperedges of $\orH$, such that each vertex receives at most $k$ positive signs from its incident hyperedges. When $k$ is large enough, we determine the threshold of the existence of a $(w,k)$ -orientation of a random hypergraph. The $(w,k)$ -orientation of hypergraphs is strongly related to a general version of the off-line load balancing problem. The graph case, when $h=2$ and $w=1$ , was solved recently by Cain, Sanders and Wormald and independently by Fernholz and Ramachandran, which settled a conjecture of Karp and Saks.

preprint2010arXiv

The diameter of sparse random graphs

In this paper we study the diameter of the random graph $G(n,p)$ , i.e., the the largest finite distance between two vertices, for a wide range of functions $p=p(n)$ . For $p=\la/n$ with $\la>1$ constant, we give a simple proof of an essentially best possible result, with an $O_p(1)$ additive correction term. Using similar techniques, we establish 2-point concentration in the case that $np\to\infty$ . For $p=(1+ε)/n$ with $ε\to 0$ , we obtain a corresponding result that applies all the way down to the scaling window of the phase transition, with an $O_p(1/ε)$ additive correction term whose (appropriately scaled) limiting distribution we describe. Combined with earlier results, our new results complete the determination of the diameter of the random graph $G(n,p)$ to an accuracy of the order of its standard deviation (or better), for all functions $p=p(n)$ . Throughout we use branching process methods, rather than the more common approach of separate analysis of the 2-core and the trees attached to it.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Nicholas Wormald

Research overview

Is this your work?

12 publications

Fast uniform generation of random graphs with given degree sequences

Uniform generation of random regular graphs

Enumeration of graphs with a heavy-tailed degree sequence

The mixing time of the giant component of a random graph

Cycle factors and renewal theory

On the degree distribution of a growing network model

The threshold for combs in random graphs

Asymptotic enumeration of sparse 2-connected graphs

Asymptotic enumeration of strongly connected digraphs by vertices and edges

Induced subgraphs in sparse random graphs with given degree sequence

Orientability thresholds for random hypergraphs

The diameter of sparse random graphs

See the researcher in context

Building this map preview