Independent set count and independent transversal connectedness
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.
The Centre for Teaching and Learning invites colleagues to apply for the Oxford Teaching, Learning and Educational Leadership Recognition Scheme accredited by Advance HE. The scheme includes a strong emphasis on recognition and educational leadership and is designed for staff who teach and support learning to achieve fellowships of the Higher Education Academy, including professional services staff.
The Summer Internship Programme offers a wide range of paid or funded internships in the UK and internationally across diverse sectors and organisations. These in person, remote, and hybrid opportunities run for 2-12 weeks during the long vacation and are exclusively available to Oxford students, from first year undergraduates to final year DPhils. International opportunities in 25 countries are advertised now, with further roles released on a rolling basis through to May.
