L4

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.

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).