New lower bounds for sphere packings and independence sets via randomness

Graph Theory Seminar
Tuesday, February 6, 2024 - 3:30pm for 1 hour (actually 50 minutes)
Skiles 006
Marcus Michelen – University of Illinois, Chicago – michelen@uic.edu
Evelyne Smith-Roberge

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.