CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Random graphs
Org: Lutz Warnke (Georgia Institute of Technology, USA)

JANE GAO, University of Waterloo
Linear time uniform generation of random matrices with prescribed marginals  [PDF]

We give a linear time algorithm to uniformly generate a random $m\times n$ matrix with nonnegative integer entries, where the sums for each row and each column are prescribed. Our algorithm is based on switchings and a novel rejection scheme. Our rejection scheme requires small computation time, and is key to obtaining a linear run time. Using this rejection scheme we improve several switching-based algorithms on generation of other discrete objects. For instance, we obtain a linear time algorithm to uniformly generate random $d$-regular graphs. All previously known samplers have run time at least $d^3n$.

The number of spanning trees in random regular uniform hypergraphs  [PDF]

The small subgraph conditioning method, introduced by Robinson and Wormald in 1992, has been used to prove several results about the structure of random regular graphs. There are fewer applications of the method to hypergraphs. I will discuss some work in progress, using small subgraph conditioning to investigate the distribution of the number of spanning trees in random regular uniform hypergraphs. (Joint work with Gary Liang, UNSW.)

Logic of sparse random graphs  [PDF]

We briefly survey results on limiting probabilities of graph properties expressible in first order logic for two models of sparse random graphs: the classical model G(n,p) when p = c/n, and random planar graphs and related classes of graphs under the uniform distribution.

PAWEL PRALAT, Ryerson University
$k$-regular subgraphs near the $k$-core threshold of a random graph  [PDF]

We prove that the binomial random graph $G_{n,p=c/n}$ with high probability has a $k$-regular subgraph if $c$ is at least $e^{-\Theta(k)}$ above the threshold for the appearance of a subgraph with minimum degree at least $k$; i.e. an non-empty $k$-core. In particular, this pins down the threshold for the appearance of a $k$-regular subgraph to a window of size $e^{-\Theta(k)}$. (Joint work with Dieter Mitsche and Mike Molloy.)

LUTZ WARNKE, Georgia Tech
The phase transition in the random d-process  [PDF]

One of the most interesting features of Erdös-Rényi random graphs is the `phase transition', where the global structure changes from only small components to a single giant component plus small ones.

In this talk we discuss the phase transition in the random d-process, which corresponds to a natural algorithmic model for generating random regular graphs that differs from the usual configuration model (starting with an empty graph on n vertices, the random d-process evolves by sequentially adding new random edges so that the maximum degree remains at most d).

Based on joint works with Nick Wormald and Laura Eslava, respectively.