Rutgers Discrete Mathematics Seminar

Title: Spin Systems on Random Regular Graphs

Speaker: Eric Vigoda, Georgia Tech

Date: Monday, February 15, 2016 2:00 pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


We'll look at the behavior of spin systems on random regular, bipartite graphs and how it relates to phase transitions on regular trees. We present a new approach for the analysis of such graphs. This yields new results for hardness of approximating the partition function for the hard-core model on weighted independent sets and for counting the number of k-colorings of a graph.

The talk is based on joint work with Andreas Galanis (Oxford) and Daniel Stefankovic (Rochester).