Computer Science/Discrete Mathematics Seminar I

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, a related fact is called "reflection positivity"). This fact contains many results in extremal graph theory and in the theory of quasirandom graphs. Using properties of this matrix, one can define and characterize "convergence" for a sequence of graphs whose size tends to infinity, and construct a limit object from which the limiting values of many graph parameters can be read off. This is closely related to "property testing" in computer science, and to "mean field theories" in statistical physics. This is joint work with many people, including Christian Borgs, Jennifer Chayes, Mike Freedman, Jeff Kahn, Lex Schrijver, Vera Sos, Balazs Szegedy, Kati Vesztergombi and Dominic Welsh.