L4

In recent years, a more top-down approach to renormalisation for singular SPDEs has emerged within the theory of regularity structures, based on regularity structures of multi-indices. This approach adopts a geometric viewpoint, aiming to stably parametrise the solution manifold rather than the larger space of renormalised objects that typically arise in fixed-point formulations of the equation. While several works have established the construction of the renormalised data (the model) in this setting, less has been shown with regards to the corresponding solution theory since the intrinsic nature of the model leads to renormalised data that is too lean to apply Hairer’s fixed-point approach.

In this talk, I will discuss past and ongoing work with L. Broux and F. Otto addressing this issue for the Phi^4 equation in its full subcritical regime. We establish local and global well-posedness within the framework of regularity structures of multi-indices; first in a space-time periodic setting and subsequently in domains with Dirichlet boundary conditions.

It is a classical result that a random permutation of $n$ elements has, on average, about $\log n$ cycles. We generalise this fact to all directed $d$-regular graphs on $n$ vertices by showing that, on average, a random cycle-factor of such a graph has $\mathcal{O}((n\log d)/d)$ cycles. This is tight up to the constant factor and improves the best previous bound of the form $\mathcal{O}({n/\sqrt{\log d}})$ due to Vishnoi. It also yields randomised polynomial-time algorithms for finding such a cycle-factor and for finding a tour of length $(1+\mathcal{O}((\log d)/d)) \cdot n$ if the graph is connected. The latter result makes progress on a restriction of the Traveling Salesman Problem to regular graphs, a problem studied by Vishnoi and by Feige, Ravi, and Singh. Our proof uses the language of entropy to exploit the fact that the upper and lower bounds on the number of perfect matchings in regular bipartite graphs are extremely close.

This talk is based on joint work with Micha Christoph, Nemanja Draganić, António Girão, Eoin Hurley, and Alp Müyesser.

For a tree $T$ whose bipartition classes have sizes $t_1 \ge t_2$, two simple constructions shows that the Ramsey number of $T$ is at least $\max\{t_1+2t_2,2t_1\}-1$. In 1974, Burr conjectured that equality holds for every tree. It turns out that Burr’s conjecture is false for certain trees called the double stars, though all of the known counterexamples have large maximum degrees. In 2002, Haxell, Łuczak, and Tingley showed that Burr’s conjecture is approximately true if one imposes a maximum degree condition.

We show that Burr’s conjecture holds for all trees with up to small linear maximum degrees. That is, there exists $c>0$ such that for every $n$-vertex tree $T$ with maximum degree at most $cn$ and bipartition class sizes $t_1\ge t_2$, its Ramsey number $R(T)$ is exactly $\max\{t_1+2t_2,2t_1\}-1$. We also generalise this result to determine the exact asymmetric Ramsey number $R(T,S)$ of two trees $T$ and $S$ under certain additional conditions, and construct examples showing that these conditions are necessary. 

This talk is based on joint work with Richard Montgomery and Matías Pavez-Signé.

Colour Refinement is a combinatorial method that distinguishes vertices in graphs based on their local neighborhood structure. By encoding these local properties into vertex colours that are refined iteratively, the process eventually stabilises into a final colouring which serves as an isomorphism test on a large class of graphs.

The central complexity parameter of the algorithm is the number of iterations required to reach stabilisation. For $n$-vertex graphs, the upper bound is $n−1$. We call graphs that attain this maximum long-refinement graphs. Their final colourings are discrete, meaning every vertex is uniquely identified by its colour.  For a long time, it was not clear whether such graphs actually exist. My talk provides an overview of the history of this graph class and reports on recent work towards a full characterisation of it.

By restricting our scope to graphs with small degrees, we have constructed infinite families of long-refinement graphs. Furthermore, by reverse-engineering connections between colour classes, we obtained a complete classification of long-refinement graphs with small (or, equivalently, large) degrees. This analysis offers deep insights into the dynamics of the refinement process, revealing that all long-refinement graphs with maximum degree 3 can be described by compact strings over a remarkably small alphabet.

The talk is based on collaborations with Brendan D. McKay and T. Devini de Mel.

An edge-colouring of a graph $G$ can fail to be rainbow for two reasons: either it contains a monochromatic cherry (a pair of incident edges), or a monochromatic matching of size two. A colouring is a proper colouring if it forbids the first structure, and a star-colouring if it forbids the second structure. I will talk about the problem of determining the maximum number of colours in a star-colouring of a large complete graph which does not contain a rainbow copy of a given graph $H$. This problem is a special case of one studied by Axenovich and Iverson on generalised Ramsey numbers.

Joint work with Allan Lo, Klas Markström, Dhruv Mubayi, Maya Stein and Lea Weber.

I discuss two separate projects which evoke/strengthen connections between combinatorics and ideas from statistical physics.

The first concerns the minimum number of independent sets in triangle-free graphs of a given edge-density. We present a lower bound using a generalisation of the inductive method of Shearer (1983) for the sharpest-to-date off-diagonal Ramsey upper bound. This result is matched remarkably closely by the count in binomial random graphs.

The second sets out a qualitative generalisation of a well-known sharp result of Haxell (2001) for independent transversals in vertex-partitioned graphs of given maximum degree. That is, we consider the space of independent transversals under one-vertex modifications. We show it is connected if the parts are strictly larger than twice the maximum degree, and if the requirement is only at least twice the maximum degree we find an interesting sufficient condition for connectivity.

These constitute joint works with Pjotr Buys, Jan van den Heuvel, and Kenta Ozeki.

If time permits, I sketch some thoughts about a systematic pursuit of more connections of this flavour.

A temporal graph $G$ is a sequence of graphs $G_1, G_2, \ldots, G_t$ on the same vertex set. In this talk, we are interested in the analogue of the Travelling Salesman Problem for temporal graphs. It is referred to in the literature as the Temporal Exploration Problem, and asks for the minimum length of an exploration of the graph, that is, a sequence of vertices such that at each time step $t$, one either stays at the same vertex or moves along a single edge of $G_t$.

One natural and still open case is when each graph $G_t$ is connected and has bounded maximum degree. We present a short proof that any such graph admits an exploration in $O(n^{3/2}\sqrt{\log n})$ time steps. In fact, we deduce this result from a more general statement by introducing the notion of average temporal maximum degree. This more general statement improves the previous best bounds, under a unified approach, for several studied exploration problems.

This is based on joint work with Carla Groenland, Lukas Michel and Clément Rambaud.

I will report on ongoing joint work with Sam Fisher on showing that the mapping class group has a finite index subgroup whose group ring embeds in a division ring. Our methods involve p-adic analytic groups, but no prior knowledge of this will be assumed and much of the talk will be devoted to explaining some of the underlying theory. Time permitting, I will also discuss some consequences for the profinite topology for the mapping class group and potential extensions to Out(RAAG).