Penny Haxell (University of Waterloo)
Algorithms for Independent Transversals and Reconfiguration
An independent transversal (IT) of a graph G with a given vertex partition P is an independent set in G consisting of one vertex in each of the parts of P. This is a very general notion, and many problems in mathematics can be expressed by asking whether a particular graph G with a particular choice of P has an IT. Various criteria involving properties of G and P are known that will guarantee the existence of an IT in G.
More broadly, one may wish to consider the space of all IT's for a given G and P, and investigate how they are related. For example, under what conditions is this space connected, in the sense that one can transition from any IT to any other via a sequence of single-vertex modifications? It has been shown (Buys-Kang-Ozeki, Wdowinski) that with conditions only very slightly stronger than those ensuring the existence of a single IT, this connectivity property also holds.
Here we consider the algorithmic version of this question, and show that under certain similarly minimal conditions, such reconfiguration paths in the space of all IT's can be found efficiently.
Rob Morris (IMPA)
Recent results in Ramsey theory
Over the past few years there have been a series of remarkable breakthroughs in graph Ramsey theory. In this talk we will discuss several of these, including exponential improvements for the diagonal, near-diagonal, and multicolor Ramsey numbers, improved lower bounds on R(3,k) and R(4,k), and an exponential upper bound on the induced Ramsey numbers.
