Schedule

An l-cycle decomposition of a graph G is a set of l-cycles in G whose edge sets partition the edge set of G. The l-cycle decomposition threshold δC_l  is then the least real number such that any n-vertex graph G with minimum degree at least (δC_l +o(1))n has an l-cycle decomposition if and only if l divides |E(G)| and each vertex of G has even degree.

Nash-Williams' famous conjecture on triangle decompositions states, asymptotically, that δC_3 

= 3/4. A very recent breakthrough result of Delcourt and Postle completely resolved this conjecture, however, Glock, Kühn, and Osthus have posed the problem of determining δC_l for larger odd values of l (the behaviour of δC_l for even l is different and well understood). A natural generalisation of Nash-Williams' conjecture implies that δC_l = l/(2l-2) for all odd l ≥ 3. Here we prove that this conjecture holds for all l ≥ 73.

This is joint work with Daniel Horsley.

Coarse graph theory is a developing area, which focuses on the large-scale geometric structure of graphs, particularly through the lens of quasi-isometry.  A central goal here is to find coarse analogues of classical graph-theoretic results.  We discuss some current progress in this direction. Joint work with Tung Nguyen and Paul Seymour.

Temporal graphs are dynamic graphs where the edge set can change in each time step, while the vertex set stays the same. The temporal exploration problem asks for a walk in a given temporal graph, where at most one edge is traversed in each time step, all vertices must be visited, and we assume the walker can see all future graphs in the sequence. It is known that there are n-vertex temporal graphs which are connected in each time step but require Ω(n2) steps to explore. Our aim is to understand what happens against a random temporal graph sequence. 

To achieve this we introduce a simple but (in our opinion) natural model specified by a measure μ supported on a set of (labelled) spanning trees of a static n-vertex graph G, where a random temporal graph is obtained by sampling a spanning tree from μ independently at each time step. Note that having a tree at each time step captures the worst case for the exploration time. Our main result is that, for any pair (μ, G), with high probability there is a schedule which explores the corresponding temporal graph in time O(n3/2)  and this bound is tight. I will also chat about some other related results of us and others.

This is joint work with Samuel Baguley, Andreas Göbel, Nicolas Klodt, George Skretas, and Viktor Zamaraev.

For graphs G, H1, ..., Hr, we say that 'G has the vertex-Ramsey property for H1, ..., Hr' if whenever we colour the vertices of G with colours from {1, ..., r} we produce a monochromatic copy of Hi in colour i for some i in {1, ..., r}. In 2020, Das, Morris and Treglown initiated an investigation of the vertex Ramsey property in the randomly perturbed setting. Building on Das, Morris and Treglown's work, we determine for any graphs H1, ..., Hr the number of random edges one must add to a dense graph to ensure that asymptotically almost surely the resulting graph has the vertex Ramsey property for H1, ..., Hr. Joint work with Victor Falgas-Ravry and Asier Calbet. 

If there is time, I will mention some upcoming work with Matthew Jenssen, Robert Hancock and Mael Kupperschmitt on sharp asymmetric vertex-Ramsey properties in G(n,p).

TBD