CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Probabilistic methods
Président: Jane Gao (University of Waterloo)

MIKHAIL ISAEV, Monash University
Distribution of tree parameters via martingale CLT  [PDF]

Tree parameters, like pattern or symmetry counts, have been extensively studied in the literature for various random models of trees. It is known, in particular, that many important examples exhibit normal or log-normal limit law. A typical approach relies on the recursive nature of trees and properties of its generating functions. We propose a purely probabilistic argument based on the general theory of Central Limit Theorems for martingales. For the uniform random labelled tree, we find the limiting distribution of parameters which are stable (in some sense) with respect to local perturbations of a tree structure. Our results are general enough to get the asymptotical normality of the number of occurrences of a fixed pattern, the asymptotical log-normality of the number of automorphisms and many more.

This is a joint work with A. Southwell (Monash University) and M. E. Zhukovskii (Moscow Institute of Physics and Technology).

OLEKSII OMELCHENKO, Simon Fraser University
Satisfiability Threshold for Power Law Random 2-SAT derived from Configuration Model  [PDF]

The random Satisfiability problem has been intensively studied for decades. However, uniform random SAT instances do not capture all the properties we observe in real-world problems. One suggested property is that industrial instances often exhibit power-law degree distributions, unlike the binomial distribution in the uniform random SAT.

In this talk we consider the random $k$-SAT problems distributed accordingly a wide range of power-law-like distributions. More precisely, we assume that the degree $\xi$ of a variable is sampled such that its right tail $F_{\xi+}(x)$ satisfies the condition $F_{\xi+}(\ell)=\Theta\left(\ell^{-\alpha}\right)$ for some $\alpha>0$. The main goal is to study the satisfiability threshold phenomenon of such formulas. For 2-SAT we locate the satisfiability threshold, and prove it only depends on the relation between the first and second moments of $\xi$. Also, for $k$-SAT, $k>2$, we conjecture that a satisfiability threshold also exists and identify lower and upper bounds on its location.

PETER OTTO, Willamette University
Vector multiplicative coalescent processes and mean minimal spanning trees of multipartite graphs  [PDF]

It is known that in certain cases, the cluster dynamics of a random graph process can be replicated with the corresponding random coalescent process. The cluster sizes of the coalescent process are reflected in a auxiliary process called the Marcus-Lushnikov process. On the other hand, the cluster sizes of the corresponding random graph process yields the mean length of minimal spanning trees with random edge lengths. This connection allows one to express the limiting mean length of minimal spanning trees in terms of the solutions of the Smoluchowski coagulation equations that represent the hydrodynamic limit of the Marcus-Lushnikov process. In this talk, I will present joint work on breaching the gap between the Smoluchowski coagulation equations for Marcus-Lushnikov processes and the theory of random graphs, concentrating on the case of regular and irregular multipartite graphs and deriving the limiting mean length of minimal spanning trees for these sequences of graphs.

IGOR SHINKAR, Simon Fraser University
On Coloring Random Subgraphs of a Fixed Graph  [PDF]

Given an arbitrary graph $G$ we study the chromatic number of a random subgraph $G_{1/2}$ obtained from $G$ by removing each edge independently with probability $1/2$. Studying $\chi(G_{1/2})$ has been suggested by Bukh, who asked whether $E[\chi(G_{1/2})] \geq \Omega( \chi(G)/\log(\chi(G)))$ holds for all graphs $G$. In this work we show that for any graph $G$ with chromatic number $k = \chi(G)$ and for all $d \leq k^{1/3}$ it holds that $\Pr[\chi(G_{1/2}) \leq d] < \exp \left(- \Omega\left(\frac{k(k-d^3)}{d^3}\right)\right)$. In particular, $\Pr[G_{1/2} \text{ is bipartite}] < \exp \left(- \Omega \left(k^2 \right)\right)$, which is tight up to a constant in $\Omega(\cdot)$, as can be seen by letting $G$ be the complete graph on $k$ vertices.

ALEXANDRA WESOLEK, Simon Fraser University
Bootstrap percolation in Ore-type graphs  [PDF]

Given a graph, we start with an initial set of infected vertices and a new vertex gets infected as soon as it has $r$ infected neighbours. Under which conditions on the graph can we find a small initially infected set that infects all of the graph, i.e. that is percolating? Gunderson showed that if a graph $G$ on $n$ vertices has minimum degree $\delta(G) \geq \lfloor n/2 \rfloor+r-3 $, then we can always find a percolating set of size $r$ (if $r\geq 4$ and $n$ is big enough). How much can we decrease the minimum degree conditions if we are initially allowed to infect $r+k$ vertices? What if we consider more general graphs that satisfy an Ore-type condition where the sum of the degrees of any two non-adjacent vertices $x$ and $y$ is bounded from below? This talk gives answers to both of those open questions.