• home

Abstract: It is well known that a maximal planar graph of order at least 3 is 3-colourable if and only if it is Eulerian. It is also known that if a maximal planar graph of order at least 3 has exactly two vertices of odd degree, then these vertices are nonadjacent. I will show that these two results are equivalent.

The talk should be accessible to undergraduate students with a basic knowledge of graph theory.

Abstract: Products of permutations are used to model problems in fields ranging from representation theory and algebraic geometry to topological graph theory. I will show how probability can be used to study such problems, with a focus on how graphs may be embedded on different surfaces.

Abstract
The 15-puzzle which acts as an inspiration for this talk is a simple game consisting of 15 square tiles numbered 1–15 in a frame that is 4 tiles high and 4 tiles wide, leaving one unoccupied tile position. Tiles in the same row or column of the open position can be moved by sliding them horizontally or vertically. Like the popular Rubik's cube, the sliding puzzle is often ‘jumbled up‘ and the goal of the puzzle is to place the tiles in numerical order from left to right and top to bottom with the empty tile in the bottom right corner. In the late 1980’s a famous American puzzler named Sam Loyd offered $1000 to anyone who could provide him with a series of moves that would swap only the tiles labelled 14 and 15 while leaving all other positions in their standard numerical order. In this talk we will discuss which mathematical principles guaranteed that Sam Loyd would keep his money and discuss how the mathematician Richard Wilson used graph theory ‘inception’ to generalize this notion to all sliding puzzles, determining exactly which solutions were possible and which could never be obtained.

The Helly number of a set in the plane is the smallest N such that the following is true. If any N members of a finite family of convex sets contains a point of S, then there is a point of S which is contained in all members of the family. An exponential lattice with base x consists of points whose coordinates are positive integer powers of x. We prove lower and upper bounds on Helly numbers of exponential lattices in terms of x, and we determine their values exactly in some cases. We also consider asymmetric exponential lattices, and characterise those that have finite Helly numbers.

Joint work with Gergely Ambrus, Martin Balko, Attila Jung and Márton Naszódi.

Abstract: I'll show an algorithm for 3 colouring triangle free graphs embedded on the Klein bottle that runs in polynomial time if most of the faces are 4 faces. Joint work with Jean-Sebastian Sereni and Zdenek Dvorak.

Abstract: The arboricity \Gamma(G) of an undirected graph G = (V,E) is the minimal number such that E can be partitioned into \Gamma(G) forests. Nash-Williams' formula states that \Gamma(G) = \ceil{ \gamma(G) }, where \gamma(G) is the maximum of |E_H|/(|V_H|-1) over all subgraphs (V_H, E_H) of G with |V_H| ≥ 2.

The Strong Nine Dragon Tree Conjecture states that if \gamma(G) ≤ k + d / (d+k+1) for natural numbers k, d, then there is a partition of the edge set of G into k+1 forests such that one forest has at most d edges in each connected component.

We settle the conjecture for d ≤ k + 1. For d ≤ 2(k+1), we cannot prove the conjecture, however we show that there exists a partition in which the connected components in one forest have at most d + \ceil{kd/(k+1)} - k edges.

As an application of this theorem, we show that every 5-edge-connected planar graph G has a 5/6-thin spanning tree, a spanning trees whose edges fill up at most 5/6 of every cut. This theorem is best possible, in the sense that we cannot replace 5-edge-connected with 4-edge-connected, even if we replace 5/6 with any positive real number less than 1. This strengthens a result of Merker and Postle which showed 6-edge-connected planar graphs have a 18/19-thin spanning tree. This is joint work with Benjamin Moore.

Abstract: Given a graph H, an edge-coloured graph G is H-rainbow saturated if it does not contain a rainbow copy of H, but the addition of any non-edge in any colour creates a rainbow copy of H. The rainbow saturation number, denoted by rsat(n,H), is the minimum number of edges among all H-rainbow saturated edge-coloured graphs on n vertices. We prove that, for any non-empty graph H, the rainbow saturation number is linear in n. This confirms a recent conjecture of Girão, Lewis, and Popielarz. Based on joint work with Natalie Behague, Tom Johnston, Shoham Letzter, and Natasha Morrison.

Abstract: Given a finite simple graph $G$, an {\em odd cover of $G$} is a collection of complete bipartite graphs, or bicliques, in which each edge of $G$ appears in an odd number of bicliques and each non-edge of $G$ appears in an even number of bicliques. We denote the minimum cardinality of an odd cover of $G$ by $b_2(G)$ and prove that $b_2(G)$ is bounded below by half of the rank over $\mathbb{F}_2$ of the adjacency matrix of $G$. We show that this lower bound is tight in the case when $G$ is a bipartite graph and almost tight when $G$ is an odd cycle. However, we also present an infinite family of graphs which shows that this lower bound can be arbitrarily far away from $b_2(G)$. Babai and Frankl (1992) proposed the ``odd cover problem," which in our language is equivalent to determining $b_2(K_n)$. Radhakrishnan, Sen, and Vishwanathan (2000) determined $b_2(K_n)$ for an infinite but density zero subset of positive integers $n$. In this paper, we determine $b_2(K_n)$ for a density $3/8$ subset of the positive integers. This is joint work with Calum Buchanan, Alexander Clifton, Jason O'Neil, Puck Rombach, and Mei Yin.

A broadcast on a connected graph G with vertex set V(G) is a function f:V(G) ➛ {0, 1, ..., diam(G)} such that f(v) ≤ e(v), where e(v) denotes the eccentricity of v. If f(v) > 0, the vertex v is said to broadcast at strength f(v). In generalizing independent sets to broadcasts, Erwin (2001) introduced the concept of hearing independent broadcasts, in which no broadcasting vertex u lies within distance f(v) of another broadcasting vertex v. If instead we require that the distance d(u, v) is at least f(u)+f(v) for all u, v with f(u), f(v) > 1, we obtain the definition of boundary independence introduced by Mynhardt and Neilson in 2019.

In this talk, we consider the minimum costs of maximal hearing independent and boundary independent broadcasts on graphs and show these parameters are comparable, solving an open problem posed by Marchessault and Mynhardt in 2021. We further prove that the minimum cost of a maximal boundary independent broadcast on a connected graph equals the minimum among those of its spanning trees, and that the same is true for hearing independent broadcasts.

Recently, Mohar introduced a variant of the cops and robber game that is played on geodesic spaces. The game combines properties of pursuit-evasion games with the classical cops and robber game played on graphs. In this talk we discuss the rules of the game and strategies for the players when the game is played on compact surfaces of constant curvature. Joint work with Vesna Iršič and Bojan Mohar.

The first two problems are concerning edge-colorings of complete graphs. Erd\H{o}s and Tuza asked in 1993 whether for any graph F on l edges and any completely balanced coloring of any sufficiently large complete graph using l colors contains a rainbow copy of F. We answer this and a related question. This is joint work with Maria Axenovich.

The third problem concerns point sets in the plane. Bárány and Füredi asked to determine the maximum number of triangles being almost similar to a given triangle in a planar point set of fixed size. Exploring connections to hypergraph Turán problems, we answer this question for almost all triangles. This is joint work with József Balogh and Bernard Lidick\'{y}.

Abstract:
The set of stable matchings induces a distributive lattice. The supremum of the stable matching lattice is the boy-optimal (girl-pessimal) stable matching and the infimum is the girl-optimal (boy-pessimal) stable matching. The classical boy-proposal deferred-acceptance algorithm returns the supremum of the lattice, that is, the boy-optimal stable matching. In this paper, we study the smallest group of girls, called the minimum winning coalition of girls, that can act strategically, but independently, to force the boy-proposal deferred-acceptance algorithm to output the girl-optimal stable matching. We characterize the minimum winning coalition in terms of stable matching rotations and show that its cardinality can take on any value between $0$ and $\floor{\frac{n}{2}}$, for instances with $n$ boys and $n$ girls. Our two main results concern the random matching model. First, the expected cardinality of the minimum winning coalition is small, specifically $(\frac{1}{2}+o(1))\log{n}$. This resolves a conjecture of Kupfer. Second, in contrast, a randomly selected coalition must contain nearly every girl to ensure it is a winning coalition asymptotically almost surely. Equivalently, for any $\varepsilon>0$, the probability a random group of $(1-\varepsilon)n$ girls is not a winning coalition is at least $\delta(\varepsilon)>0$. This is joint work with Sergey Norin and Adrian Vetta.

Abstract: A spanning tree is a connected subgraph of a graph with no cycles. I will explain some well-known connection between such collection of trees and some Poissonian collection of loops, and a magical algorithm (known as Wilson's alorithm) to sample such trees very fast. Then I will try to explain a recent extension to the multiply connected setting, and pose an open question in the end. Joint work with N. Berestycki and B. Laslier.

Abstract: A classical result, due to Bollobás and Thomason, and independently Komlós and Szemerédi, states that a graph with average degree O(k^2) guarantees the existence of a K_k-subdivision. We study two directions extending this result.

Firstly, Verstraëte conjectured in 2002 that the quadratic bound O(k^2) would guarantee already two vertex-disjoint isomorphic copies of a K_k-subdivision. Secondly, Thomassen conjectured in 1984 that for each k \in \mathbb{N} there is some d = d(k) such that every graph with average degree at least d contains a balanced subdivision of K_k. Recently, Liu and Montgomery confirmed Thomassen's conjecture, but the optimal bound on d(k) remains open.

In this talk, we show that the quadratic bound O(k^2) suffices to force a balanced K_k-subdivision. This gives the optimal bound on d(k) needed in Thomassen's conjecture and implies the existence of O(1) many vertex-disjoint isomorphic K_k-subdivisions, confirming Verstraëte's conjecture in a strong sense.

Abstract:
In the biased Hamilton Cycle Maker-Breaker game, two players alternate choosing edges from a complete graph. In the game with bias b, Maker chooses one previously unchosen edge in each turn and Breaker chooses b. The game is Maker-win for the given bias if Maker can ensure she chooses the edges of a Hamilton Cycle and Breaker-win otherwise.

Letting n be the number of vertices, if the bias is 0 then Maker wins the game in n moves. On the other hand, if the bias b=b(n) is {n choose 2}-1 then Breaker wins. Furthermore, if Breaker wins for some bias b, then she also wins for bias b+1. We discuss the threshold at which the game becomes Breaker win, and the number of moves maker needs to ensure she wins for b below this threshold, which is called the speed of the game.

Warmup: What bounds can you obtain on the threshold and speed without a literature search? Any ideas how to proceed?