University of Warwick

The saturation number of a graph is a famous and well-studied counterpoint to the Turán number, and the rainbow saturation number is a generalisation of the saturation number to the setting of coloured graphs. Specifically, for a given graph $F$, an edge-coloured graph is $F$-rainbow saturated if it does not contain a rainbow copy of $F$, but the addition of any non-edge in any colour creates a rainbow copy of $F$. The rainbow saturation number of $F$ is the minimum number of edges in an $F$-rainbow saturated graph on $n$ vertices. Girão, Lewis, and Popielarz conjectured that, like the saturation number, for all $F$ the rainbow saturation number is linear in $n$. I will present our attractive and elementary proof of this conjecture, and finish with a discussion of related results and open questions.

Add to calendar

Brown-Erdős-Sós initiated the study of the maximum number of edges in an $n$-vertex $r$-graph such that no $k$ edges span at most $s$ vertices. If $s=rk-2k+2$ then this function is quadratic in $n$ and its asymptotic was previously known for $k=2,3,4$. I will present joint work with Stefan Glock, Jaehoon Kim, Lyuben Lichev and Shumin Sun where we resolve the cases $k=5,6,7$.

Graph braid groups are similar to braid groups, except that they are defined as ‘braids’ on a graph, rather than the real plane. We can think of graph braid groups in terms of the discrete configuration space of a graph, which is a CW-complex. One can compute a presentation of a graph braid group using Morse theory. In this talk I will give a few examples on how to compute these presentations in terms of generating circuits of the graph. I will then go through a detailed example of a graph that gives a one-ended braid group.

For integers $k \ge 1$ and $n \ge 2k+1$, the Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of an $n$-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph $K(5,2)$. This problem received considerable attention in the literature, including a recent solution for the sparsest case $n=2k+1$. The main contribution of our work is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph $J(n,k,s)$ has as vertices all $k$-element subsets of an $n$-element ground set, and an edge between any two sets whose intersection has size exactly $s$. Clearly, we have $K(n,k)=J(n,k,0)$, i.e., generalized Johnson graphs include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász' conjecture on Hamilton cycles in vertex-transitive graphs from 1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life, and to analyze this system combinatorially and via linear algebra.

This is joint work with my students Arturo Merino (TU Berlin) and Namrata (Warwick).

We study “bottom-up” models for the collective motion of large groups of animals. Similar models can be encoded into (micro)robotic matter, capable of sensing light and processing information. Agents are endowed only with visual sensing and information processing. We study a model in which moving agents reorientate to maximise the path-entropy of their visual environment over paths into the future. There are general arguments that principles like this that are based on retaining freedom in the future may confer fitness in an uncertain world. Alternative “top-down” models are more common in the literature. These typically encode coalignment and/or cohesion directly and are often motivated by models drawn from physics, e.g. describing spin systems. However, such models can usually give little insight into how co-alignment and cohesion emerge because these properties are encoded in the model at the outset, in a top-down manner. We discuss how our model leads to dynamics with striking similarities with animal systems, including the emergence of coalignment, cohesion, a characteristic density scaling anddifferent behavioural phenotypes. The dynamics also supports a very unusual order-disorder transition in which the order (coalignment) initially increases upon the addition of sensory or behavioural noise, before decreasing as the noise becomes larger.

Many congruences between modular forms (or at least their q-expansions) can be explained by the theory of $p$-adic families of modular forms. In this talk, I will discuss properties of eigenvarieties, a geometric interpretation of the idea of $p$-adic families. In particular, focusing initially on the well-understood case of (elliptic) modular forms, before delving into the considerably murkier world of Bianchi modular forms. In this second case, this work gives numerical verification of a couple of conjectures, including BSD by work of Loeffler and Zerbes.

We will use Representation Theory to calculate systematically and efficiently the topological invariants of compact Lie groups and homogeneous spaces.
 

Most of the talk is covered by our second paper on ArXiv with John Jones and Adam Thomas, who are both at Warwick. The paper is part of the ongoing project to study the topological invariants of the four exceptional Rosenfeld projective planes.

We determine the minimal forbidden minors characterising the class of countable graphs that embed into some compact surface. We will also discuss Thomas’s conjecture that the Robertson—Seymour Graph Minor Theorem extends to countably infinite graphs. [https://arxiv.org/abs/2301.11042]