Georgia Institute of Technology College of Sciences

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.

Turán-type problems ask for the densest-possible structure which avoids a fixed substructure H. Ramsey-type problems ask for the largest possible "complete" structure which can be decomposed into a fixed number of H-free parts. We discuss some of these problems in the context of vector spaces over finite fields. In the Turán setting, Furstenberg and Katznelson showed that any constant-density subset of the affine space AG(n,q) must contain a k-dimensional affine subspace if n is large enough. On the Ramsey side of things, a classical result of Graham, Leeb, and Rothschild implies that any red-blue coloring of the projective space PG(n-1,q) must contain a monochromatic k-dimensional projective subspace, for n large. We highlight the connection between these results and show how to obtain new bounds in the latter (projective Ramsey) problem from bounds in the former (affine Turán) problem. This is joint work with Liana Yepremyan.

The well-known tree packing conjecture of Gyárfás from 1976 says that, given any sequence of n trees in which the ith tree has i vertices, the trees can be packed edge-disjointly into the complete n-vertex graph. Packing even just the largest trees in such a sequence has proven difficult, with Bollobás drawing attention to this in 1995 by conjecturing that, for each k, if n is sufficiently large then the largest k trees in any such sequence can be packed. This has only been shown for k at most 5, by Zak, despite many partial results and much related work on the full tree packing conjecture.

I will discuss a result which proves Bollobás's conjecture by showing that, moreover, a linear number of the largest trees can be packed in the tree packing conjecture. This is joint work with Barnabás Janzer.

We consider the algorithmic problem of finding large balanced independent sets in sparse random bipartite graphs, and more generally the problem of finding independent sets with specified proportions of vertices on each side of the bipartition. In a bipartite graph it is trivial to find an independent set of density at least half (take one of the partition classes). In contrast, in a random bipartite graph of average degree d, the largest balanced independent sets (containing equal number of vertices from each class) are typically of density (2 + od(1)) log d/d . Can we find such large balanced independent sets in these graphs efficiently? By utilizing the overlap gap property and the low-degree algorithmic framework, we prove that local and low-degree algorithms (even those that know the bipartition) cannot find balanced independent sets of density greater than (1 + ε) log d/d for any ε > 0 fixed and d large but constant.