Title: On the average size of independent sets in triangle-free graphs
|Affiliation:||University of Waterloo|
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  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  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.
200 University Avenue West
Waterloo, ON N2L 3G1