• home

Abstract: A classic result of Chvatál and Erdős (1972) asserts that, if the vertex-connectivity of a graph G is at least as large as its independence number, then G has a Hamilton cycle. We prove a similar result, implying that a graph G is pancyclic, namely it contains cycles of all lengths between 3 and |G|: we show that if |G| is large and the vertex-connectivity of G is larger than its independence number, then G is pancyclic. This confirms a conjecture of Jackson and Ordaz (1990) for large graphs.

Abstract: A famous result of Rado characterises those integer matrices $A$ which are partition regular, that is, for which any finite colouring of $[n]:=\{1,2,\dots,n\}$ (for $n$ sufficiently large) gives rise to a monochromatic solution to the equation $Ax=0$. The probability threshold for when the binomial random set $[n]_p$ has the property above was established via results of R\"odl and Ruci\'nski (for the 0-statement), and Friedgut, R\"odl and Schacht (for the 1-statement). Collectively these results form the Random Rado Theorem.

There has also been interest in Rado-type results in the setting of abelian groups. In this talk we prove an analogue of the Random Rado Theorem in the setting of sequences of (subsets of) abelian groups.

Joint work with Andrea Freschi and Andrew Treglown.

Abstract: The Manickam-Miklós-Singhi Conjecture states that for positive integers n and k with n > (4k - 1), a multi-set X = {x_1,x_2, … ,x_n} with real entries and nonnegative sum has at least \binom{n-1}{k-1} subsets of size k with nonnegative sum.

Abstract: In 2017, Ron Aharoni proposed the following generalization of the Caccetta-Häggkvist conjecture: if G is a simple n-vertex edge-colored graph with n color classes of size at least r, then G contains a rainbow cycle of length at most the ceiling of n/r.

I will begin with a summary of recent progress on Aharoni's conjecture based on a new survey article of Katie Clinch, Jackson Goerner, Freddie Illingworth, and myself. I will then sketch a proof that Aharoni's conjecture holds up to an additive constant for each fixed r. The last result is joint work with Patrick Hompe.

Abstract: A collection of families $(\F_{1}, \F_{2} , \cdots , \F_{k}) \in \mathcal{P}([n])^k$ is \emph{cross-Sperner} if there is no pair $i \not= j$ for which some $F_i \in \F_i$ is comparable to some $F_j \in \F_j$. Two natural measures of the `size' of such a family are the sum $\sum_{i = 1}^k |\F_i|$ and the product $\prod_{i = 1}^k |\F_i|$. We prove upper and lower bounds on the sum measure for general $n$ and $k \ge 2$. In the process, we consider minimizing the number of sets comparable to a family $\F \subseteq \mathcal{P}([n])$ of a given size.

Abstract: An $(m,n)$-generalized bent function is a function from $\mathbb{Z}_2^n$ to $\mathbb{Z}_m$ so that its associated Fourier transformations have constant absolute value. It is known that an $(m,n)$-generalized bent function exists whenever one of the following holds:

1. both $m$ and $n$ are even.
2. $4 \mid m$.

Abstract: If a tricky devil challenged you to complete a Sudoku puzzle of their design, what restrictions could you place on their design to guarantee it was impossible for them to thwart your attempts? More specifically, if you could dictate exactly how many times that devil could use each symbol or pre-fill any one row, column, or box, could you safely bet that their deviously designed puzzle was still completable? This notion of seeking out guaranteed completability conditions for Sudoku drives the discussion as we delve into various graph and matrix representations of the Sudoku, explore relaxed notions of completability such as fractional completability, and use these tools to approach an answer. Due to the ongoing nature of this research, this talk is designed to serve as an introduction to the machinery of the argument being employed but does not conclude with a definitive answer.

Abstract: Suppose we have a set P of n points in the plane, and another set S of n^{1/3} points in convex position. What can we say about the structure of this arrangement if P contains many translates of the set S? I will discuss a recent result showing that if P contains around n translates of S, then the translation vectors must come from a generalized arithmetic progression of low dimension.

The motivation for this problem comes from incidence geometry, where many constructions for strictly convex curves having many incidences with pointsets follow this general outline. In particular, I will discuss applications to the Erdos unit distance conjecture. This is joint work with Jozsef Solymosi and Ethan White.

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 1880’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.