Reading Group on Entropy and Counting - John Schanck

Title: On the average size of independent sets in triangle-free graphs

Abstract:

Some of the results that we've seen in this reading group have been improved recently using the "hard-core model" from statistical physics. We'll introduce the hard-core model and discuss a result from Davies, Jenssen, Perkins, and Roberts [1] that relates the average size of an independent set in a triangle-free graph to the free-energy of the hard-core model on that graph. This result gives an alternative proof of Shearer's upper bound on the Ramsey number R(3, k).

The same proof technique has been used by Jenssen, Joos, and Perkins to re-derive  Rogers' lower bound on maximum sphere packing density, and to improve the Chabauty--Shannon--Wyner lower bound on the maximum size of a spherical code of a given angle. The hard-core model has also been used [2] to prove Brégman's theorem, the Kahn--Lovász theorem, Conjecture 7.1 from Galvin's lecture notes, and the asymptotic upper matching conjecture.

[1] https://arxiv.org/abs/1606.01043

[2] https://arxiv.org/pdf/1508.04675