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.

TBA

Speaker Edward Tansley will talk about: 'Low-rank functions in machine learning'

Functions that vary along a low-dimensional subspace of their input space, often called multi-index or low-rank functions, frequently arise in machine learning. Understanding how such structure emerges can provide insight into the learning dynamics of neural networks. One line of work that explores how networks learn low-rank data representations is the Neural Feature Ansatz (NFA), which states that after training, the Gram matrix of the first-layer weights of a deep network is proportional to some power of the average gradient outer product (AGOP) of the network with respect to its inputs. Existing results prove this relationship for 2-layer linear networks under balanced initialization. In this work, we extend these results to general L-layer linear networks and remove the assumption of balanced initialization for networks trained with weight decay.