Georgia Institute of Technology College of Sciences

Thomassen famously showed that every planar graph is 5-choosable, and that every planar graph of girth at least five is 3-choosable.  These theorems are best possible for uniform list assignments: Voigt gave a construction of a planar graph that is not 4-choosable, and of a planar graph of girth four that is not 3-choosable. In this talk, I will introduce the concept of a local girth list assignment: a list assignment wherein the list size of each vertex depends not on the girth of the graph, but only on the length of the shortest cycle in which the vertex is contained. I will present a local list colouring theorem that unifies the two theorems of Thomassen mentioned above and discuss some of the highlights and difficulties of the proof. This is joint work with Luke Postle.

Given a divergence-free vector field on the torus, we consider the mixing properties of the associated flow. There is a rich body of work studying the dependence of the mixing scale on various norms of the vector field. We will discuss some interesting examples of vector fields that mix at the optimal rate, and an improved bound on the mixing scale under the extra assumption that the vector field is a shear at each time.

The Prophet Inequality and Pandora's Box problems are fundamental stochastic problems. A usual assumption for both problems is that the probability distributions of the n underlying random variables are given as input to the algorithm. In this talk, we assume the distributions are unknown, and study them in the Multi-Armed Bandits model: We interact with the unknown distributions over T rounds. In each round we play a policy and receive only bandit feedback. The goal is to minimize the regret, which is the difference in the total value of the optimal algorithm that knows the distributions vs. the total value of our algorithm that learns the distributions from the bandit feedback. Our main results give near-optimal  O(poly(n)sqrt{T}) total regret algorithms for both Prophet Inequality and Pandora's Box.

An order-n Latin square is an $n \times n$ matrix with entries from a set of $n$ symbols, such that each row and each column contains each symbol exactly once.  Suppose that $L_{i,j} \subseteq [n]$ is a random subset of $[n]$ where each $k \in [n]$ is included in $L_{i,j}$ independently with probability $p$ for each $i,j\in[n]$.  How likely does there exist an order-$n$ Latin square where the entry in the $i$th row and $j$th column lies in $L_{i,j}$?  This question was initially raised by Johansson in 2006, and later Casselgren and H{\"a}ggkvist and independently Luria and Simkin conjectured that $\log n / n$ is the threshold for this property.  In joint work with Dong-yeap Kang, Daniela K\"{u}hn, Abhishek Methuku, and Deryk Osthus, we proved that for some absolute constant $C$, if $p > C \log^2 n / n$, then asymptotically almost surely there exists such a Latin square.  We also prove analogous results for Steiner triple systems and $1$-factorizations of complete graphs.