CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Analytic and Probabilistic Techniques in Combinatorics - Part II
Org: Jan Volec (Emory University and Universitat Hamburg)

ROBERT HANCOCK, Masaryk University
Some results in 1-independent percolation  [PDF]

We obtain an improved lower bound for the threshold probability $p_c$, for which every $1$-independent measure with bond density $p>p_c$ percolates on the lattice $\mathbb{Z}^2$. We also present further results motivated by $1$-independent percolation: for any connected graph $G$, let $f_{G}(p)$ be the infimum over all $1$-independent measures $\mu$ with bond density $p$ of the probability that a $\mu$-random graph is connected. We obtain lower bounds for $f_{G}(p)$ for paths, ladders, complete graphs and cycles, and provide constructions giving matching upper bounds for paths, complete graphs and small cycles. Joint work with A. Nicholas Day and Victor Falgas-Ravry.

GUILHERME OLIVEIRA MOTA, Universidade Federal do ABC
The multicolour size-Ramsey number of powers of paths  [PDF]

Given a positive integer $s$, a graph $G$ is $s$-Ramsey for a graph $H$, denoted $G\rightarrow (H)_s$, if every $s$-colouring of the edges of $G$ contains a monochromatic copy of $H$. The $s$-colour size-Ramsey number $\hat{r}_s(H)$ of a graph $H$ is defined to be $\hat{r}_s(H)=\min\{|E(G)|\colon G\rightarrow (H)_s\}$. We prove that, for every positive integers $k$ and $s$, we have $\hat{r}_s(P_n^k)=O(n)$, where $P_n^k$ is the $k$th power of the $n$-vertex path $P_n$.

This is a joint work with Jie Han, Matthew Jenssen, Yoshiharu Kohayakawa and Barnaby Roberts.

ROBERT ŠÁMAL, Charles University
A rainbow version of Mantel's Theorem  [PDF]

Let $G_1,G_2,G_3$ be simple graphs on a common vertex set and think of each graph as having edges of a distinct colour. A rainbow triangle has three vertices $v_1,v_2,v_3$ so that $v_iv_{i+1}\in{}E(G_i)$. We show that if $|E(G_i)|>(\frac{26-2\sqrt{7}}{81})n^2\approx0.2557n^2$ for $i=1,2,3$, then there exists a rainbow triangle, thereby answering a question of Diwan and Mubayi. Our result is sharp in the sense that the multiplicative constant cannot be decreased.

This is joint work with R.Aharoni, M.DeVos, S.Gonzales and A.Montejano. We prove the result from first principles. An independent proof using flag algebra method was obtained by E.Culver, B.Lidický, F.Pfender, and J.Volec.

MARYAM SHARIFZADEH, University of Warwick
Graphons with minimum clique density  [PDF]

Among all graphs of given order and size, we determine the asymptotic structure of graphs which minimise the number of $r$-cliques, for each fixed $r$. In fact, this is achieved by characterising all graphons with given density which minimise the $K_r$-density. The case $r=3$ was proved in 2016 by Pikhurko and Razborov. This is joint work with H. Liu, J. Kim, and O. Pikhurko.