Tutte Prize
Président:
Douglas B. West (Zhejiang Normal University and University of Illinois)
[
PDF]
 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.
 LIANNA HAMBARDZUMYAN, McGill University
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) 173176.
 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 pathmetric space is an EPPAwitness for itself. Cherlin gave a list of such graphs (by describing the classes of finite subspaces of their pathmetric spaces) and Aranda et al. determined the existence of EPPAwitnesses 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 automorphismpreserving 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 neartriangulations, 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)$.