CanaDAM 2015
University of Saskatchewan, June 1 - 4, 2015

Random graphs
Organizer and Chair: Pawel Pralat (Ryerson University, Canada)

TOM BOHMAN, Carnegie Mellon University
Dynamic concentration in random greedy processes  [PDF]

Let ${\mathcal H}$ be a $D$-regular, $r$-uniform hypergraph on $n$ vertices, where $r$ is fixed and $D \to \infty$ as $n \to \infty$. In this talk we survey some recent results on the random greedy matching algorithm and the random greedy independent set algorithm applied to ${\mathcal H}$. These random processes have implications for some classical questions in combinatorics. In this talk we focus on the questions that remain open.

On Hamilton Cycles in Random Hypergraphs  [PDF]

In this talk, we present both old and new developments concerning the Hamiltonicity of random hypergraphs. First, we consider random $k$-uniform hypergraphs of order~$n$ (each possible $k$-tuple appears independently with probability~$p$) and determine the thresholds for the existence of different types of Hamilton cycles (including loose and tight cycles). Next, we discuss some very recent results about Hamiltonicity of random regular hypergraphs (joint work with Alan Frieze, Andrzej Ruci\'nski, and Matas \v{S}ileikis). In doing so, we partially answer a question of Kim and Vu about ``sandwiching random graphs''.

LINCOLN LU, University of South Carolina
Subgraphs in Random Non-uniform Hypergraphs  [PDF]

For a given set of positive integers $R:=\{k_1,k_2,\ldots, k_r\}$ and probabilities ${\bf p}=(p_1,p_2,\ldots, p_r)\in [0,1]^r$, let $G^R(n, {\bf p})$ be the random hypergraph $G$ on $n$ vertices so that for $1\leq i\leq r$ each $k_i$-subset of vertices appears as an edge of $G$ with probability $p_i$ independently. We ask for what probability vector $\bf{p}$, $G^R(n,\bf{p})$ almost surely contains a given subhypergraph $H$. Those $\bf{p}$ for which $G^R(n,{ \bf p})$ almost surely contains $H$, form a convex region (depending on $H$) in a log-scale drawing. We also consider the associated extension problems. (Joint work with Edward Boehnlein.)

ABBAS MEHRABIAN, Pacific Institute for the Mathematical Sciences
Why complex networks have logarithmic diameters?  [PDF]

We present a new technique for proving logarithmic upper bounds for diameters of evolving random graph models, which is based on defining a coupling between random graphs and variants of random recursive trees. This technique is quite simple and provides short proofs, is applicable to a broad variety of models including those incorporating preferential attachment, and provides bounds with small constants. We illustrate this by proving logarithmic upper bounds for diameters of the following well-known models: forest fire model, copying model, PageRank-based selection model, Aiello-Chung-Lu models, generalized linear preference model, directed scale-free graphs, Cooper-Frieze model, and random unordered increasing $k$-trees.

TOBIAS MULLER, Utrecht University
Connectivity and the largest component in a hyperbolic model for complex networks  [PDF]

In this talk, I will discuss some recent and ongoing work on a model for complex networks that was introduced recently by Krioukov et al. In this model, N points are chosen randomly on the hyperbolic plane and any two of them are joined by an edge if they are within a certain hyperbolic distance. The model exhibits a power-law degree sequence, small distances and clustering. I will present some results on the component structure of the graph model, and on the probability that it is connected.

(based on joint work with Michel Bode and Nikolaos Fountoulakis)

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society University of Saskatchewan