Abstract. Gibbs measures play a prominent role in several areas of mathematics from probability and statistical physics, to combinatorics, to computer science. In each role, the central object of interest is the partition function, the normalizing constant of the probability distribution. In graph theory, these partition functions correspond to graph polynomials such as the independence polynomial or the matching polynomial. I will present a new method for proving extremal bounds on graph polynomials and on the number of independent sets, matchings, and colorings in various classes of graphs by optimizing probabilistic observables in relevant models from statistical physics (e.g., the hard-core, monomer-dimer, and Potts models) via linear programming relaxations. Based on joint work with E. Davies, M. Jenssen, and B. Roberts.
Collins Conference Room
Seminar
US Mountain Time
Speaker:
Will Perkins (University of Birmingham)
Our campus is closed to the public for this event.