Please note that the list below only shows forthcoming events, which may not include regular events that have not yet been entered for the forthcoming term. Please see the past events page for a list of all seminar series that the department has on offer.
Tue, 17 Feb 2026
14:00 -
15:00
L4
Independent set count and independent transversal connectedness
Ross Kang
(University of Amsterdam)
Abstract
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.