Let $H$ be an induced subgraph of the torus $C_k^n$. We discuss results concerning when the vertices or edges of $C_k^n$ can be decomposed into induced copies of $H$. In particular, we disprove a conjecture of Gruslys, showing that when k is odd and not a prime power, then there exists $H$ such that $|V(H)|$ divides some power of $k$, but there is no n such that the vertices of $C_k^n$ can be decomposed into copies of $H$. We also disprove a conjecture of Gruslys, Leader and Tan on edge decomposing $C_k^n$. Joint work with Marthe Bonamy and Alex Scott.

The Erdős distance problem is to find a bound on the minimum number of distinct distances that a point set can determine in the real plane. This was resolved (up to a logarithmic factor and to much acclaim) by Guth and Katz over the real plane. One can also ask this question over other fields, in particular finite fields. Here, not all of the techniques used by Guth and Katz are applicable. Indeed, we do ask this question: in joint work with Brendan Murphy, we show how to employ incidence bounds to obtain a new result on the Erdős distance problem over $\mathbb{F}_p$.

Given a finite subset $A$ of integers and co-prime natural numbers $q,s$, we consider the set $q\cdot A + s\cdot A$, that is, the sum of dilates of $A$. In recent years, finding suitable lower bounds for the cardinality of such sets in terms of $|A|, q$ and $s$ has seen considerable activity. In 2014, Balog and Shakan found sharp estimates for the same, that were tight in both the main term as well as the error term. Subsequently, they considered this problem in higher dimensional integer lattices. In this talk, we present a short survey of these results including our own improvement in the higher dimensional setting.

Products of simplices are important polytopes that have multiple applications to game theory, optimisation and algebraic geometry. Moreover, their structure and subdivisions lay the groundwork for the theory of products of more general polytopes, and so a great deal of study has gone into them. A beautiful fact is that their subdivisions may be encoded via a set of bipartite graphs satisfying certain compatibility conditions, and so we can remove all geometry and work strictly in the realm of combinatorics. In this talk we shall demonstrate how this graphical characterisation is possible. Furthermore, we shall consider a secondary description in terms of pairs of compositions, and as a corollary derive the first bounds on the number of triangulations of a product of simplices. This is joint work with Georg Loho.

The Firefighter game offers a simple, discrete time model for the spread of a perfectly infectious disease and the effect of vaccination. A fire breaks out on a graph at time $0$ on a set $F$ of $f$ vertices. At most $d$ non-burning vertices are then defended and can not burn in future. Vertices, once either burning or defended remain so for the rest of the game. At each subsequent time step, the fire spreads deterministically to all neighbouring undefended vertices and then at most $d$ more vertices can be defended. The game ends when the fire can spread no further. Determining whether $k$ vertices can be saved is NP-complete. I focus on finding maximal minimal damage (mmd) graphs - graphs which have the least burning if the fire starts in the worst place and the defenders defend optimally. I shall present some new and old results linking mmd graphs to optimal graphs for the Resistance Network Problem of finding graphs where all $F$-sets of vertices have limited neighbourhoods.

The local resilience of a graph $G$ with respect to a property $\mathcal{P}$ measures how much one has to change $G$ locally in order to destroy $\mathcal{P}$. We prove 'resilience' versions of several classical results for the graph models $G_{n,p}$ and $G_{n,d}$.
For example, we prove a resilience version of Dirac's theorem in the setting of random regular graphs. More precisely, we show that, whenever $d$ is sufficiently large compared to $\varepsilon>0$, a.a.s. the following holds: any subgraph of the random $n$-vertex $d$-regular graph $G_{n,d}$ with minimum degree at least $(1/2+\varepsilon)d$ is Hamiltonian. This proves a conjecture of Ben-Shimon, Krivelevich and Sudakov.
We also prove a resilience version of Pósa’s Hamiltonicity condition for the binomial random graph $G_{n,p}$ and show that a natural guess for a resilient version of Chvátal’s theorem for $G_{n,p}$ fails to be true.
This is joint work with Padraig Condon, António Girão, Jaehoon Kim, Daniela Kühn and Deryk Osthus.

In this talk we introduce a new research tool, an online interactive repository of graphs called the Online Graph Atlas (OLGA). The repository is designed to enable efficient retrieval of information about graphs and to enable queries based on combinations of standard graph parameters. Parameters include chromatic number, chromatic index, domination number, independence number, clique number, matching number, vertex cover number, size of automorphism group, vertex connectivity, edge connectivity, eigenvalues, treewidth, and genus.
Inspired by Read and Wilson's book, An Atlas of Graphs (OUP, 1998), Barnes, Bonnington and Farr developed the first prototype of OLGA in 2009, which was extended by Sio, Farr and Bonnington in 2010 by adding more parameters. We change its design to make it more flexible and extendable. We also introduce new parameters such as chromatic index, chromatic number, degeneracy, eigenvalues, size of automorphism group, treewidth and Tutte polynomial. OLGA now stores over 20 standard parameters for each graph of up to 10 vertices. We used recursive algorithms and exact algorithms for parameter computation. OLGA is not limited to the role of a search engine for graphs. We demonstrate how to use OLGA as a tool to explore conjectures and theorems involving the parameters.
This is joint work with Graham Farr, Paul Bonnington, and Kerri Morgan.

In the usual form of a combinatorial game, two players take turns to play moves in a set (the 'board'), and certain subsets are designated as 'winning': the first player to occupy such a set wins the game. For these games, it is well known that (with correct play) the game cannot be a second-player win.
In the 'misère' form, the first person to occupy such a set loses the game. Here it would be natural to assume that the game cannot be a first-player win, at least if the game is transitive, meaning that all points of the board look the same. Our aim is to investigate this.
This is joint work with Robert Johnson and Mark Walters.

We study the positional game where two players, Maker and Breaker, alternately select respectively $1$ and $b$ previously unclaimed edges of $K_n$. Maker wins if she succeeds in claiming all edges of some odd cycle in $K_n$ and Breaker wins otherwise. Improving on a result of Bednarska and Pikhurko, we show that Maker wins the odd cycle game if $b \leq \big( (4 - \sqrt6)/5 + o(1) \big) n$. We furthermore introduce "connected rules" and study the odd cycle game under them, both in the Maker-Breaker as well as in the Client-Waiter variant.
This is joint work with Jan Corsten, Adva Mond, Alexey Pokrovskiy and Tibor Szabó.

For a graph $G=(V,E)$, a hypergraph $\mathcal{H}$ is called a Berge-$G$, denoted by $BG$, if there exists an bijection $f: E(G) \rightarrow E(\mathcal{H})$ such that for every $e \in E(G)$, $e \subseteq f(e)$. Let the Ramsey number $R^r(BG,BG)$ be the smallest integer $n$ such that for any $2$-edge-coloring of a complete $r$-uniform hypergraph on $n$ vertices, there is a monochromatic Berge-$G$ subhypergraph. In this paper, we show that the 2-color Ramsey number of Berge cliques is linear. In particular, we show that $R^3(BK_s, BK_t) = s+t-3$ for $s,t \geq 4$ and $\max(s,t) \geq 5$ where $BK_n$ is a Berge-$K_n$ hypergraph. For higher uniformity, we show that $R^4(BK_t, BK_t) = t+1$ for $t\geq 6$ and $R^k(BK_t, BK_t)=t$ for $k \geq 5$ and $t$ sufficiently large. We also investigate the Ramsey number of trace hypergraphs, suspension hypergraphs and expansion hypergraphs.

Lehel conjectured that every red/blue edge-colouring of the complete graph admits a vertex partition into a red cycle and a blue cycle. This conjecture was proved by Bessy and Thomassé in 2010.
We consider a generalisation of Lehel's conjecture to hypergraphs.In particular we prove that every red/blue edge-colouring of the complete \(4\)-uniform hypergraph contains a red and a blue tight cycle such that their union covers almost all vertices.
This is joint work with Allan Lo.

How many bicliques (complete bipartite graphs) are needed to decompose the edge set of the complete graph on $n$ vertices? There are many ways to do this with $n - 1$ bicliques, and indeed the Graham-Pollak Theorem states that one can do no better.
What happens for hypergraphs? For example, how many complete biclique 3-graphs do we need to decompose the complete 3-graph on $n$ vertices? In this light talk, I will give a short algebraic proof of a linear lower bound.

A question of Graham and Pollak asks for the minimal number of bicliques (complete bipartite graphs) required to partition the edges of $K_n$. Any proof that linearly many are required is algebraic in nature. Mubayi and Vishwanathan derived a non-trivial lower bound for the problem in a purely combinatorial way, considering the chromatic number of an edge-disjoint union of bicliques. In this talk, I will discuss a generalisation of their result to uniform hypergraphs, and a combinatorial lower bound for a new generalisation of the Graham-Pollak problem.

A 1-factorization of a graph $H$ is a partition of the edges of $H$ into disjoint perfect matchings $\{M_1,M_2,\ldots,M_n\}$, also known as 1-factors. A 1-factorization $\mathcal{M} = \{M_1,M_2,\ldots,M_n\}$ of a graph $G$ is called perfect if the union of any pair of 1-factors $M_i, M_j$ with $i \ne j$ is a Hamilton cycle.
The existence or non-existence of perfect 1-factorizations has been studied for various families of graphs. Perhaps the most famous open problem in the area is Kotzig's conjecture, which states that the complete graph $K_{2n}$ has a perfect 1-factorization.
In my work I have focused on another well-studied family of graphs: the hypercubes $Q_d$ in $d$ dimensions. There is no perfect 1-factorization of $Q_d$ for $d>2$. As a result, we need to consider a weaker concept.
A 1-factorization $\mathcal{M}$ is called $k$-semi-perfect if the union of any pair of 1-factors $M_i, M_j$ with $1 \le i \le k$ and $k+1 \le j \le n$ is a Hamilton cycle. It was proved that there is a 1-semi-perfect 1-factorization of $Q_d$ for every integer $d \ge 2$ by Gochev and Gotchev, Královič and Královič, and Chitra and Muthusamy, in answer to a conjecture of Craft.
My main result is a proof that there is a $k$-semi-perfect 1-factorization of $Q_d$ for all $k$ and all $d$, except for one possible exception when $k=3$ and $d=6$.
I will conclude with some questions concerning other generalisations of perfect 1-factorizations.

Given graphs \(G\) and \(H\), we define an \(H\)-tiling in \(G\) to be a collection of vertex-disjoint copies of \(H\) in \(G\). Let \(\varepsilon > 0\). We call an \(H\)-tiling perfect if it covers all of the vertices in \(G\) and \(\varepsilon\)-almost perfect if it covers all but at most an \(\varepsilon\)-proportion of the vertices in \(G\). An important theorem of Komlós provides the minimum degree of \(G\) which ensures an \(\varepsilon\)-almost perfect \(H\)-tiling in \(G\). We present a degree sequence strengthening of this result. (Joint work with Hong Liu and Andrew Treglown.)
Using the aforementioned theorem of Komlós, Kühn and Osthus determined the minimum degree of \(G\) that ensures a perfect \(H\)-tiling in \(G\). We present a degree sequence version of their result as an application of our degree sequence Komlós theorem. (Joint work with Andrew Treglown.)

In 1981 Jackson showed that the diregular bipartite tournament (a complete balanced bipartite graph whose edges are oriented so that every vertex has the same in- and outdegree) contains a Hamilton cycle, and conjectured that in fact the edge set of it can be partitioned into Hamilton cycles. We prove an approximate version of this conjecture: For every $c>1/2$ there is an $\varepsilon>0$ such that for large $n$ every balanced bipartite digraph on $2n$ vertices with minimum semidegree $cn$ contains $(1-\varepsilon)cn$ edge-disjoint Hamilton cycles. This is joint work with Anita Liebenau (UNSW Sydney).

Several times I've made progress on a problem by asking a computer to work out some properties of a small example. Often the answer itself is interesting. But sometimes it feels like just as much value comes from having thought about something in enough detail to explain it to a computer.
I'll explain how using computers has helped me to think about some problems, focusing on understanding maximal left-compressed intersecting families of sets.

In this talk, we obtain quantitative bounds for Brauer's generalisation of van der Waerden's theorem. Brauer's theorem states that there exists a positive integer $\mathrm{B}(r,k)$ such that any $r$-colouring of the set $\{1,2,...,\mathrm{B}(r,k)\}$ yields a monochromatic $k$-term arithmetic progression which receives the same colour as its common difference. By modifying the work of Gowers on Szemerédi's theorem, we show that the quantity $\mathrm{B}(r,k)$ can be taken to be double exponential in the number of colours $r$, and quintuple exponential in the length $k$.
This talk is based on joint work with Sean Prendiville.

Additive combinatorics studies the presence of patterns such as arithmetic progressions in subsets of natural numbers or abelian groups. These structures can be examined using ideas from combinatorics, number theory, analysis and dynamics. One of the best known results in the area is Szemerédi theorem, which states that each dense subset of natural numbers contains an arithmetic progression of arbitrary length. Among its generalisations is a result of Bergelson and Leibman, who showed that each dense subset of natural numbers contains a polynomial progression $x, x+P_1(y), \dots, x+P_m(y)$ for arbitrary polynomials $P_1, \ldots, P_m$ having zero constant terms. This talk will discuss the theorem of Bergelson and Leibman together with recent developments.

Suppose we run a train on a directed (multi-)graph, where every vertex has out-degree 2 and is equipped with a switch. At the beginning, the switch at each vertex points to one of the two outgoing edges. When the train reaches a vertex, it will traverse along the edge pointed by the switch, and then the switch at that vertex shifts to the other outgoing edge. Given such a graph with an origin vertex $o$ and a destination vertex $d$, the problem is to decide if the train starting from $o$ can reach $d$.
The problem above is called ARRIVAL. It is known that the problem is in NP and co-NP. The open question is whether it is in P. Potentially, a polynomial-time algorithm may be devised by modelling the problem as an integer programme and examining the primal and dual of the linear relaxation.
In this talk, I will present a combinatorial algorithm that runs in time $O(2^{n/2})$. This is based on joint work with Bernd Gärtner.

The key objective behind compressed sensing is to solve the underdetermined linear system $A \boldsymbol{x} = \boldsymbol{b}$ where A is $m \times n$ matrix with $m < n$ and $\boldsymbol{b}$ is a vector. Solving this system under the additional assumption that $\boldsymbol{x}$ is from a finite-valued set and sparse i.e., most of its entries are zero, appears in several applications including science and engineering. Using the $\ell_0$-minimisation to solve this system is known to be $\mathcal{NP}$-hard. Despite this one approach resulting in a solution is to use the $\ell_1$-minimisation to find the minimal solution and apply the well-known Null Space Property (NSP) which guarantees the uniqueness of that solution leading to exact recovery. This talk will discuss a weakened version of the NSP with particular reference to several examples.

We present an algorithm for solving feasibility of real-number linear programs in standard form $Ax = b, x \geq 0$ where $A \in \mathbb{R}^{m \times n}, x \in \mathbb{R}^n, b \in \mathbb{R}^m$. In particular, we present a recursive algorithm using primal-dual interior-point methods that solves feasibility within $\mathcal{O}(n^{1.5}\log\bar\chi_A)$ iterations, where $\bar\chi_A$ is a condition measure of $A$ that was introduced by Dikin. This is a significant improvement over the best previous result by Ye, who developed a two-layered interior-point method that runs for $\mathcal{O}(n^{2.5}\log\bar\chi_A)$ iterations. It is widely assumed that feasibility can not be solved significantly faster than optimization. Thus, we suggest that the current best interior-point method based algorithm that runs in $\mathcal{O}(n^{3.5}\log\bar\chi_A)$ iterations can be improved. We outline how to approach optimality with the techniques developed for feasibility.
This is joint work with Daniel Dadush, Sophie Huiberts and László Végh.

A classical problem of Erdős and Sós asks to determine the Turán number of a tree. We consider variants of this problem in the settings of hypergraphs and multi-hypergraphs. In particular, we determine a bound which is sharp for infinitely values of $n$ for the Turán number of a hypergraph without a Berge copy of a tree with $k$ edges, for all $k$ and $r$, $r \ge k\cdot (k-2)$. We also characterize the extremal hypergraphs in the cases of equality.
The results discussed in the talk are joint work with Ervin Győri, Nika Salia and Casey Tompkins.

Tree decompositions have been very successfully employed in the design of parameterized graph algorithms. Typically an upper bound on the running time of such algorithms depends on the width of the decomposition provided: i.e the size of its largest bag. For this reason much effort has been directed towards finding tree decompositions with minimum width. However, this is not the right way of constructing an 'algorithmically best' tree decomposition because the width of a tree decomposition which minimizes the running time of some algorithm is not always minimum. The intuition behind this phenomenon is that it is sometimes better to allow a few large bags in order to accommodate many small bags.
This talk will will address progress related to the question:
"is the width of an `algorithmically best' tree decomposition bounded with respect to treewidth?"

Let $G$ be a $d$-regular graph on $n$ vertices. For a vertex set $A \subset G$, let $e(A, \bar A)$ be the number of edges between $A$ and $\bar A$. The bisection width of $G$ is defined as \[ \operatorname{bw}(G) = \min_{\substack{A \subset G \\ |A|=\lfloor n/2 \rfloor}} e(A, \bar{A}). \] For $d \geq 4$, we show that for any $d$-regular graph $G$, \begin{align*} \operatorname{bw} (G) &\leq \left(d-3+\frac{3}{d+1}\right)\frac{n}{4} + d\mathcal O (\sqrt{n} \ln n) & \text{for $d$ even} \\ \operatorname{bw} (G) &\leq \left(d-3+\frac{8}{d+3}\right)\frac{n}{4} + d\mathcal O (\sqrt{n}) & \text{for $d$ odd}. \end{align*} As far as we know, these give the best known bounds for $4 \leq d \leq 122$ that apply to all graphs. The results hold for all $d$, but for larger $d$, a result by Alon showing that $\operatorname{bw} (G) \leq \left(d- \frac{3 \sqrt d}{8 \sqrt{2}}\right) \frac{n}{4}$ for $n$ sufficiently large is stronger. Our approach is based on a paper by Monien and Preis, using iterative local improvement and helpful sets.