Georgia Institute of Technology College of Sciences

Many problems in rigidity theory and matrix completion boil down to finding a nice combinatorial description of some matroid supported on the edge set of a complete (bipartite) graph. In this talk, I will give many such examples. My goal is to convince you that a general theory of matroids supported on graphs is needed and to give you a sense of what that could look like.

 For a graph $H$ and an $n$-vertex graph $G$, the $H$-bootstrap percolation process on $G$ is the process which starts with $G$ and, at every time step, adds any missing edges on the vertices of $G$ that complete a copy of $H$. This process eventually stabilises and we are interested in the extremal question raised by Bollob\'as, of determining the maximum \emph{running time} (number of time steps before stabilising) of this process, over all possible choices of $n$-vertex graph $G$. We initiate a systematic study of this parameter, denoted $M_H(n)$, and its dependence on properties of the graph $H$. In a series of works we determine the precise running time for cycles and asymptotic running time for several other important classes. In general, we study necessary and sufficient conditions on $H$ for fast, i.e. sublinear or linear $H$-bootstrap percolation, and in particular explore the relationship between running time and minimum vertex degree and connectivity. Furthermore we also obtain the running time of the process for typical $H$ and discover several graphs exhibiting surprising behavior.  The talk represents joint work with David Fabian and Patrick Morris.

 The study of Ramsey properties of the binomial random graph G_{n,p} was initiated in the 80s by Frankl & Rödl and Łuczak, Ruciński & Voigt. In this area we are often interested in establishing what function f(n) governs G_{n,p} having a particular Ramsey-like property P or not, i.e. when p is sufficiently larger than f(n) then G_{n,p} a.a.s. has P and when p is sufficiently smaller than f(n) then G_{n,p} a.a.s. does not have P (the former we call a 1-statement, the latter a 0-statement). I will present recent results on this topic from two different papers.

In the first, we almost completely resolve an outstanding conjecture of Kohayakawa and Kreuter on asymmetric Ramsey properties. In particular, we reduce the 0-statement to a necessary colouring problem which we solve for almost all pairs of graphs. Joint work with Candy Bowtell and Robert Hancock.

In the second, we prove similar results concerning so-called anti- and constrained-Ramsey properties. In particular, we (essentially) completely resolve the outstanding parts of the problem of determining the threshold function for the constrained-Ramsey property, and we reduce the anti-Ramsey problem to a necessary colouring problem which we prove for a specific collection of graphs. Joint work with Natalie Behague, Robert Hancock, Shoham Letzter and Natasha Morrison.

We show new lower bounds for sphere packings in high dimensions and for independent sets in graphs with not too large co-degrees.  For dimension d, this achieves a sphere packing of density (1 + o(1)) d log d / 2^(d+1).  In general dimension, this provides the first asymptotically growing improvement for sphere packing lower bounds since Roger's bound of c*d/2^d in 1947.  The proof amounts to a random (very dense) discretization together with a new theorem on constructing independent sets on graphs with not too large co-degree.  Both steps will be discussed, and no knowledge of sphere packings will be assumed or required.  This is based on joint work with Marcelo Campos, Matthew Jenssen and Julian Sahasrabudhe.