CanaDAM 2019
SFU Harbour Centre, May 29 - 31, 2019

Tutte Prize
Chair: Douglas B. West (Zhejiang Normal University and University of Illinois)

PETER BRADSHAW, Simon Fraser University
Cops and Robbers on Abelian Cayley Graphs  [PDF]

We present a strategy by which $O(\sqrt{n})$ cops can capture a robber on an abelian Cayley graph of $n$ vertices. This proves that Meyniel's conjecture holds for abelian Cayley graphs.

Chang's lemma via Pinsker's inequality  [PDF]

Extending the idea of R. Impagliazzo et al. [1] we give a short information theoretic proof for Chang's lemma that is based on Pinsker's inequality. \newline \newline [1] R. Impagliazzo, C. Moore, A. Russell, An entropic proof of chang's inequality, SIAM Journal on Discrete Mathematics 28 (1) (2014) 173-176.

MATĚJ KONEČNÝ, Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University
Extending partial isometries of antipodal graphs  [PDF]

A structure $B$ is an \emph{EPPA}-witness for a structure $A$ if $A\subseteq B$ and every isomorphism of finite substructures of $A$ extends to an automorphism of $B$. A graph $G$ is \emph{metrically homogeneous} if its path-metric space is an EPPA-witness for itself. Cherlin gave a list of such graphs (by describing the classes of finite subspaces of their path-metric spaces) and Aranda et al. determined the existence of EPPA-witnesses for almost all such classes. We resolve the remaining cases. Our result should be seen as the first application of a general method for bypassing the lack of automorphism-preserving completions.

BENJAMIN MOORE, University of Waterloo
The pseudoforest analogue of the strong nine dragon tree conjecture is true  [PDF]

We prove that for any positive integers $k$ and $d$, if a graph $G$ has maximum average degree at most $2k +\frac{2d}{d+k+1}$, then $G$ decomposes into $k+1$ pseudoforests $C_1,…,C_{k+1}$ such that there is an $i$ such that for every connected component $C$ of $C_i$, we have that $e(C) \leq d$.

MICHAL SEWERYN, Jagelonian University
Improved bound for the dimension of posets of treewidth two  [PDF]

It has long been known that posets with cover graphs of treewidth $3$ can have arbitrarily large dimension. In 2017, Joret, Micek, Trotter, Wang and Wiechert showed that posets whose cover graphs have treewidth at most $2$, have dimension at most $1276$. We improve this bound to $12$ with a much simpler proof.

ABHINAV SHANTANAM, Simon Fraser University
Minimum Balanced Bipartitions of Planar Triangulations  [PDF]

A balanced bipartition of a graph $G$ is a bipartition $(V_1, V_2)$ of $V(G)$ where $V_1$ and $V_2$ differ in size by at most $1$. A minimum balanced bipartition of $G$ is a balanced bipartition $(V_1, V_2)$ of $V(G)$ with the minimum number $e(V_1, V_2)$ of edges with ends in both $V_1$ and $V_2$. We show that, for every plane triangulation $G$, there exists a minimum balanced bipartition $(V_1, V_2)$ of $V(G)$ with $e(V_1, V_2) \leq |V(G)|$ such that both $V_1$ and $V_2$ induce connected near-triangulations, and the total number of blocks in $G[V_1]$ and $G[V_2]$ exceeds the total number of internal vertices by at most $2$. This confirms the folklore conjecture that, for any planar graph $G$, a minimum balanced bipartition $(V_1, V_2)$ of $V(G)$ has $e(V_1, V_2) \leq |V(G)|$.