|
|
|
|
|
|
|
|
Graph homomorphisms, statistical physics, and quasirandom graphs
Counting homomorphisms between graphs has a surprising number of applications. Many models in statistical mechanics and many questions in extremal graph theory can be phrased in these terms. We introduce a matrix, which we call the connection matrix, and show that this is positive semidefinite (in statistical mechanics, this fact is called "reflection positivity"). We show that this fact contains many results in extremal graph theory and in the theory of quasirandom graphs. Through this, we find interesting applications of important techniques from statistical mechanics like cluster expansion and Dobrushin uniqueness. This is joint work with many people, including Christian Borgs, Jennifer Chayes, Mike Freedman, Jeff Kahn, Lex Schrijver, Vera Sos, Kati Vesztergombi, Dominic Welsh.
Thursday, February 19, 2004, 245 Altgeld Hall, 4:00 p.m.
Mathematics Colloquia homepage