We prove that every finite colouring of the plane contains a monochromatic pair of points at an odd integral distance from each other.

Graph product structure theory describes complex graphs in terms of products of simpler graphs. In this talk, I will introduce this subject and talk about some of my recent results in this area. The focus of my talk will be on a new tool in graph product structure theory called `blocking partitions.’ I’ll show how this tool can be used to prove stronger product structure theorems for powers of planar graphs as well as k-planar graphs, resolving open problems of Dujmović, Morin and Wood, and Ossona de Mendez.

An edge-coloured graph is said to be rainbow if it uses no colour more than once. Extremal problems involving rainbow objects have been a focus of much research over the last decade as they capture the essence of a number of interesting problems in a variety of areas. A particularly intensively studied question due to Keevash, Mubayi, Sudakov and Verstraëte from 2007 asks for the maximum possible average degree of a properly edge-coloured graph on n vertices without a rainbow cycle. Improving upon a series of earlier bounds, Tomon proved an upper bound of $(\log n)^{2+o(1)}$ for this question. Very recently, Janzer-Sudakov and Kim-Lee-Liu-Tran independently removed the $o(1)$ term in Tomon's bound. We show that the answer to the question is equal to $(\log n)^{1+o(1)}$. A key tool we use is the theory of robust sublinear expanders. In addition, we observe a connection between this problem and several questions in additive number theory, allowing us to extend existing results on these questions for abelian groups to the case of non-abelian groups. Joint work with: Noga Alon, Lisa Sauermann, Dmitrii Zakharov and Or Zamir.

The k-color induced size-Ramsey number of a graph H is the smallest number of edges a (host) graph G can have such that for any k-coloring of its edges, there exists a monochromatic copy of H which is an induced subgraph of G. In 1995, in their seminal paper, Haxell, Kohayakawa and Łuczak showed that for cycles these numbers are linear for any constant number of colours, i.e., for some C=C(k), there is a graph with at most Cn edges whose any k-edge-coloring contains a monochromatic induced cycle of length n. The value of C comes from the use of the sparse regularity lemma and has a tower-type dependence on k. In this work, we obtain nearly optimal bounds for the required value of C. Joint work with Nemanja Draganić and Benny Sudakov.

Graph pebbling is a combinatorial game played on an undirected graph with an initial configuration of pebbles. A pebbling move consists of removing two pebbles from one vertex and placing one pebbling on an adjacent vertex. The pebbling number of a graph is the smallest number of pebbles necessary such that, given any initial configuration of pebbles, at least one pebble can be moved to a specified target vertex. In this talk, we will give a survey of several streams of research in pebbling, including describing a theoretical and computational framework that uses mixed-integer linear programming to obtain bounds for the pebbling numbers of graphs. We will also discuss improvements to this framework through the use of newly proved weight functions that strengthen the weight function technique of Hurlbert. Finally, we will discuss some open extremal problems in pebbling, specifically related to Class 0 graphs and describe how structural graph theoretic techniques such as discharging can be used to obtain results. Collaborators on these projects include Dan Cranson, Dominic Flocco, Luke Postle, Jonad Pulaj, Chenxiao Xue, Marshall Yang, Daniel Zhou.

Even delta-matroids generalize matroids, as they are defined by a certain basis exchange axiom weaker than that of matroids. One natural example of even delta-matroids comes from a skew-symmetric matrix over a given field $K$, and we say such an even delta-matroid is representable over the field $K$. Interestingly, a matroid is representable over $K$ in the usual manner if and only if it is representable over $K$ in the sense of even delta-matroids. The representability of matroids got much interest and was extensively studied such as excluded minors and representability over more than one field. Recently, Baker and Bowler (2019) integrated the notions of $K$-representable matroids, oriented matroids, and valuated matroids using tracts that are commutative ring-like structures in which the sum of two elements may output no element or two or more elements. We generalize Baker-Bowler's theory of matroids with coefficients in tracts to orthogonal matroids that are equivalent to even delta-matroids. We define orthogonal matroids with coefficients in tracts in terms of Wick functions, orthogonal signatures, circuit sets, and orthogonal vector sets, and establish basic properties on functoriality, duality, and minors. Our cryptomorphic definitions of orthogonal matroids over tracts provide proofs of several representation theorems for orthogonal matroids. In particular, we give a new proof that an orthogonal matroid is regular (i.e., representable over all fields) if and only if it is representable over $\mathbb{F}_2$ and $\mathbb{F}_3$, which was originally shown by Geelen (1996), and we prove that an orthogonal matroid is representable over the sixth-root-of-unity partial field if and only if it is representable over $\mathbb{F}_3$ and $\mathbb{F}_4$. This is joint work with Tong Jin.

The square of a graph $G$, denoted $G^2$, has the same vertex set as $G$ and has an edge between two vertices if the distance between them in $G$ is at most $2$. Wegner's conjecture (1977) states that for a planar graph $G$, the chromatic number $\chi(G^2)$ of $G^2$ is at most 7 if $\Delta(G) = 3$, at most $\Delta(G)+5$ if $4 \leq \Delta(G) \leq 7$, and at most $\lfloor \frac{3 \Delta(G)}{2} \rfloor$ if $\Delta(G) \geq 8$. Wegner's conjecture is still wide open. The only case for which we know tight bound is when $\Delta(G) = 3$. Thomassen (2018) showed that $\chi(G^2) \leq 7$ if $G$ is a planar graph with $\Delta(G) = 3$, which implies that Wegner's conjecture is true for $\Delta(G) = 3$. A natural question is whether $\chi_{\ell}(G^2) \leq 7$ or not if $G$ is a subcubic planar graph, where $\chi_{\ell}(G^2)$ is the list chromatic number of $G^2$. Cranston and Kim (2008) showed that $\chi_{\ell}(G^2) \leq 7$ if $G$ is a subcubic planar graph of girth at least 7. We prove that $\chi_{\ell}(G^2) \leq 7$ if $G$ is a subcubic planar graph of girth at least 6. This is joint work with Xiaopan Lian (Nankai University).

In 1986, Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa property for minor if and only if it is planar. In particular, for every non-planar graph $H$ they gave examples showing that the Erdős-Pósa property does not hold for $H$. Recently, Liu confirmed a conjecture of Thomas and showed that every graph has the half-integral Erdős-Pósa property for minors. In this talk, we start the delineation of the half-integrality of the Erdős-Pósa property for minors. We conjecture that for every graph $H$ there exists a finite family $\mathfrak{F}_H$ of parametric graphs such that $H$ has the Erdős-Pósa property in a minor-closed graph class $\mathcal{G}$ if and only if $\mathcal{G}$ excludes a minor of each of the parametric graphs in $\mathfrak{F}_H$. We prove this conjecture for the class $\mathcal{H}$ of Kuratowski-connected shallow-vortex minors by showing that, for every non-planar $H\in\mathcal{H}$ the family $\mathfrak{F}_H$ can be chosen to be precisely the two families of Robertson-Seymour counterexamples to the Erdős-Pósa property of $H$.