CanaDAM 2013
Memorial University of Newfoundland, June 10 - 13, 2013

Random Graphs
Chair: Pu Gao (University of Toronto)

DEEPAK BAL, Carnegie Mellon University
Packing Tree Factors in Random and Pseudo-Random Graphs  [PDF] [SLIDES]

For a fixed graph $H$ with $t$ vertices, an $H$-factor of a graph $G$ with $n$ vertices is a collection of vertex disjoint (not necessarily induced) copies of $H$ in $G$ covering all vertices of $G$. We prove that certain pseudo-random and random graphs may have almost all of their edges covered by a collection of edge disjoint $H$-factors in the case where $H$ is a tree.

Joint work with Alan Frieze, Michael Krivelevich and Po-Shen Loh.

KATY BEELER, Wake Forest University
Deterministic walks, fairness, and choice  [PDF]

In this talk we discuss deterministic movement over toroidal grids (and more generally, Cayley graphs), integrating local information, bounded memory and choice at individual nodes. The research is motivated by recent work on deterministic random walks, and applications in multi-agent systems. Several results regarding passing tokens through toroidal grids are discussed, as well as some open questions.

PU GAO, University of Toronto
Change of limiting distributions of the number of large matchings  [PDF] [SLIDES]

We study the asymptotic distribution of the number of matchings of size $\ell$ in G(n,p), for all $1\le \ell\le n/2$. We prove that for all $\ell=o(n\sqrt{p})$, this random variable is asymptotically distributed as a normal variable, whereas for all $\ell=\Omega(n\sqrt{p})$, its asymptotic distribution changes to log-normal.

FLORIAN LEHNER, Graz University of Technology
Automorphism breaking in locally finite graphs  [PDF] [SLIDES]

A colouring of a graph $G$ is called distinguishing if its stabiliser in $\operatorname{Aut} G$ is trivial. It has been conjectured that, if every automorphism of a locally finite graph moves infinitely many vertices, then there is a distinguishing $2$-colouring.

We investigate properties of random $2$-colourings of such graphs and show that the stabiliser of such a colouring is almost surely nowhere dense in $\operatorname{Aut} G$ and a null set with respect to the Haar measure on the automorphism group. We also mention several special cases where a random $2$-colouring is almost surely distinguishing.

CRISTIANE M. SATO, University of Waterloo
On the robustness of random k-cores  [PDF]

The $k$-core of a graph is its maximal subgraph with minimum degree $\geq k$. Choose a $k$-core u.a.r.\ from the $k$-cores with $n$ vertices and $m=m(n)$ edges, delete one edge u.a.r.\ and find the $k$-core of the new graph. The number~$z$ of vertices that have to be deleted to find the new $k$-core can be seen as a measure of robustness of the original $k$-core. If $c=2m/n\to k$, we prove that $z=n$ with probability going to $1$ as $n\to\infty$. We define a constant $c_k'$ such that when~$c<c_k'-\epsilon$, $z=n$ with positive probability and, if $c>c_k'+\epsilon$ and $c=O(1)$, $z$~is bounded in probability.

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 Memorial University of Newfoundland