Source author record

Nick 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 Discrete Mathematics Computational Geometry Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

12works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Asymptotic enumeration of hypergraphs by degree sequence

We prove an asymptotic formula for the number of $k$ -uniform hypergraphs with a given degree sequence, for a wide range of parameters. In particular, we find a formula that is asymptotically equal to the number of $d$ -regular $k$ -uniform hypergraphs on $n$ vertices provided that $dn\le c\binom{n}{k}$ for a constant $c>0$ , and $3 \leq k < n^C$ for any $C<1/9.$ Our results relate the degree sequence of a random $k$ -uniform hypergraph to a simple model of nearly independent binomial random variables, thus extending the recent results for graphs due to the second and third author.

preprint2020arXiv

Asymptotic enumeration of digraphs and bipartite graphs by degree sequence

We provide asymptotic formulae for the numbers of bipartite graphs with given degree sequence, and of loopless digraphs with given in- and out-degree sequences, for a wide range of parameters. Our results cover medium range densities and close the gaps between the results known for the sparse and dense ranges. In the case of bipartite graphs, these results were proved by Greenhill, McKay and Wang in 2006 and by Canfield, Greenhill and McKay in 2008, respectively. Our method also essentially covers the sparse range, for which much less was known in the case of loopless digraphs. For the range of densities which our results cover, they imply that the degree sequence of a random bipartite graph with m edges is accurately modelled by a sequence of independent binomial random variables, conditional upon the sum of variables in each part being equal to m. A similar model also holds for loopless digraphs.

preprint2016arXiv

The number of satisfying assignments of random regular k-SAT formulas

Let $Φ$ be a random $k$ -SAT formula in which every variable occurs precisely $d$ times positively and $d$ times negatively. Assuming that $k$ is sufficiently large and that $d$ is slightly below the critical degree where the formula becomes unsatisfiable with high probability, we determine the limiting distribution of the logarithm of the number of satisfying assignments.

preprint2016arXiv

The probability of nonexistence of a subgraph in a moderately sparse random graph

We develop a general procedure that finds recursions for statistics counting isomorphic copies of a graph $G_0$ in the common random graph models ${\cal G}(n,m)$ and ${\cal G}(n,p)$ . Our results apply when the average degrees of the random graphs are below the threshold at which each edge is included in a copy of $G_0$ . This extends an argument given earlier by the second author for $G_0=K_3$ with a more restricted range of average degree. For all strictly balanced subgraphs $G_0$ , our results gives much information on the distribution of the number of copies of $G_0$ that are not in large "clusters" of copies. The probability that a random graph in ${\cal G}(n,p)$ has no copies of $G_0$ is shown to be given asymptotically by the exponential of a power series in $n$ and $p$ , over a fairly wide range of $p$ . A corresponding result is also given for ${\cal G}(n,m)$ , which gives an asymptotic formula for the number of graphs with $n$ vertices, $m$ edges and no copies of $G_0$ , for the applicable range of $m$ . An example is given, computing the asymptotic probability that a random graph has no triangles for $p=o(n^{-7/11})$ in ${\cal G}(n,p)$ and for $m=o(n^{15/11})$ in ${\cal G}(n,m)$ , extending results of the second author.

preprint2015arXiv

Almost all 5-regular graphs have a 3-flow

Tutte conjectured in 1972 that every 4-edge connected graph has a nowhere-zero 3-flow. This has long been known to be equivalent to the conjecture that every 5-regular 4-edge-connected graph has an edge orientation in which every out-degree is either 1 or 4. We show that the assertion of the conjecture holds asymptotically almost surely for random 5-regular graphs. It follows that the conjecture holds for almost all 4-edge connected 5-regular graphs.

preprint2015arXiv

On the push&pull protocol for rumour spreading

The asynchronous push&pull protocol, a randomized distributed algorithm for spreading a rumour in a graph $G$ , works as follows. Independent Poisson clocks of rate 1 are associated with the vertices of $G$ . Initially, one vertex of $G$ knows the rumour. Whenever the clock of a vertex $x$ rings, it calls a random neighbour $y$ : if $x$ knows the rumour and $y$ does not, then $x$ tells $y$ the rumour (a push operation), and if $x$ does not know the rumour and $y$ knows it, $y$ tells $x$ the rumour (a pull operation). The average spread time of $G$ is the expected time it takes for all vertices to know the rumour, and the guaranteed spread time of $G$ is the smallest time $t$ such that with probability at least $1-1/n$ , after time $t$ all vertices know the rumour. The synchronous variant of this protocol, in which each clock rings precisely at times $1,2,\dots$ , has been studied extensively. We prove the following results for any $n$ -vertex graph: In either version, the average spread time is at most linear even if only the pull operation is used, and the guaranteed spread time is within a logarithmic factor of the average spread time, so it is $O(n\log n)$ . In the asynchronous version, both the average and guaranteed spread times are $Ω(\log n)$ . We give examples of graphs illustrating that these bounds are best possible up to constant factors. We also prove theoretical relationships between the guaranteed spread times in the two versions. Firstly, in all graphs the guaranteed spread time in the asynchronous version is within an $O(\log n)$ factor of that in the synchronous version, and this is tight. Next, we find examples of graphs whose asynchronous spread times are logarithmic, but the synchronous versions are polynomially large. Finally, we show for any graph that the ratio of the synchronous spread time to the asynchronous spread time is $O(n^{2/3})$ .

preprint2014arXiv

Asymptotic enumeration of sparse connected 3-uniform hypergraphs

We derive an asymptotic formula for the number of connected 3-uniform hypergraphs with vertex set $[N]$ and $M$ edges for $M=N/2+R$ as long as $R$ satisfies $R = o(N)$ and $R=ω(N^{1/3}\ln^{2} N)$ . This almost completely fills the gap in the range of $M$ for which the formula is known. We approach the problem using an `inside-out' approach of an earlier paper of Pittel and the second author, for connected graphs. A key part of the method uses structural components of connected hypergraphs called cores and kernels. These are structural components of connected hypergraphs. Our results also give information on the numbers of them with a given number of vertices and edges, and hence their typical size in random connected $3$ -uniform hypergraphs with $N$ vertices and $M$ edges, for the range of $M$ we consider.

preprint2014arXiv

It's a Small World for Random Surfers

We prove logarithmic upper bounds for the diameters of the random-surfer Webgraph model and the PageRank-based selection Webgraph model, confirming the small world phenomenon holds for them. In the special case when the generated graph is a tree, we provide close lower and upper bounds for the diameters of both models.

preprint2014arXiv

Longest paths in random Apollonian networks and largest $r$ -ary subtrees of random $d$ -ary recursive trees

Let $r$ and $d$ be positive integers with $r<d$ . Consider a random $d$ -ary tree constructed as follows. Start with a single vertex, and in each time-step choose a uniformly random leaf and give it $d$ newly created offspring. Let ${\mathcal T}_t$ be the tree produced after $t$ steps. We show that there exists a fixed $δ<1$ depending on $d$ and $r$ such that almost surely for all large $t$ , every $r$ -ary subtree of ${\mathcal T}_t$ has less than $t^δ$ vertices. The proof involves analysis that also yields a related result. Consider the following iterative construction of a random planar triangulation. Start with a triangle embedded in the plane. In each step, choose a bounded face uniformly at random, add a vertex inside that face and join it to the vertices of the face. In this way, one face is destroyed and three new faces are created. After $t$ steps, we obtain a random triangulated plane graph with $t+3$ vertices, which is called a random Apollonian network. We prove that there exists a fixed $δ<1$ , such that eventually every path in this graph has length less than $t^δ$ , which verifies a conjecture of Cooper and Frieze.

preprint2014arXiv

Meyniel's conjecture holds for random graphs

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph $G$ is called the cop number of $G$ . The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant $C$ , the cop number of every connected graph $G$ is at most $C \sqrt{|V(G)|}$ . In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph. We do this by first showing that the conjecture holds for a general class of graphs with some specific expansion-type properties. This will also be used in a separate paper on random $d$ -regular graphs, where we show that the conjecture holds asymptotically almost surely when $d = d(n) \ge 3$ .

preprint2013arXiv

On the Longest Paths and the Diameter in Random Apollonian Networks

We consider the following iterative construction of a random planar triangulation. Start with a triangle embedded in the plane. In each step, choose a bounded face uniformly at random, add a vertex inside that face and join it to the vertices of the face. After n-3 steps, we obtain a random triangulated plane graph with n vertices, which is called a Random Apollonian Network (RAN). We show that asymptotically almost surely (a.a.s.) every path in a RAN has length o(n), refuting a conjecture of Frieze and Tsourakakis. We also show that a RAN always has a path of length (2n-5)^{log 2/log 3}, and that the expected length of its longest path is Omega(n^0.88). Finally, we prove that a.a.s. the diameter of a RAN is asymptotic to c log n, where c \approx 1.668 is the solution of an explicit equation.

preprint2012arXiv

On the Stretch Factor of Randomly Embedded Random Graphs

We consider a random graph G(n,p) whose vertex set V has been randomly embedded in the unit square and whose edges are given weight equal to the geometric distance between their end vertices. Then each pair {u,v} of vertices have a distance in the weighted graph, and a Euclidean distance. The stretch factor of the embedded graph is defined as the maximum ratio of these two distances, over all u,v in V. We give upper and lower bounds on the stretch factor (holding asymptotically almost surely), and show that for p not too close to 0 or 1, these bounds are best possible in a certain sense. Our results imply that the stretch factor is bounded with probability tending to 1 if and only if n(1-p) tends to 0, answering a question of O'Rourke.

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.

Nick Wormald

Research overview

Is this your work?

12 publications

Asymptotic enumeration of hypergraphs by degree sequence

Asymptotic enumeration of digraphs and bipartite graphs by degree sequence

The number of satisfying assignments of random regular k-SAT formulas

The probability of nonexistence of a subgraph in a moderately sparse random graph

Almost all 5-regular graphs have a 3-flow

On the push&pull protocol for rumour spreading

Asymptotic enumeration of sparse connected 3-uniform hypergraphs

It's a Small World for Random Surfers

Longest paths in random Apollonian networks and largest $r$ -ary subtrees of random $d$ -ary recursive trees

Meyniel's conjecture holds for random graphs

On the Longest Paths and the Diameter in Random Apollonian Networks

On the Stretch Factor of Randomly Embedded Random Graphs

See the researcher in context

Building this map preview

Nick Wormald

Research overview

Is this your work?

12 publications

Asymptotic enumeration of hypergraphs by degree sequence

Asymptotic enumeration of digraphs and bipartite graphs by degree sequence

The number of satisfying assignments of random regular k-SAT formulas

The probability of nonexistence of a subgraph in a moderately sparse random graph

Almost all 5-regular graphs have a 3-flow

On the push&pull protocol for rumour spreading

Asymptotic enumeration of sparse connected 3-uniform hypergraphs

It's a Small World for Random Surfers

Longest paths in random Apollonian networks and largest rrr-ary subtrees of random ddd-ary recursive trees

Meyniel's conjecture holds for random graphs

On the Longest Paths and the Diameter in Random Apollonian Networks

On the Stretch Factor of Randomly Embedded Random Graphs

See the researcher in context

Building this map preview

Longest paths in random Apollonian networks and largest $r$ -ary subtrees of random $d$ -ary recursive trees