Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Bounding the partition function of spin-systems. | Bounding the partition function of spin-systems David J. Galvin Department of Mathematics University of Pennsylvania 209 South 33th Street Philadelphia PA 19104 USA dgalvin@ Submitted Aug 23 2005 Accepted Jul 28 2006 Published Aug 22 2006 Mathematics Subject Classifications 05C15 82B20 Abstract With a graph G V E we associate a collection of non-negative real weights UveV Ai v 1 i m u Aij uv 1 i j mg. We consider the probability distribution on f V 1 . m in which each f occurs with probability proportional to HveV Af v v riuveE Af u f v uv. Many well-known statistical physics models including the Ising model with an external field and the hard-core model with non-uniform activities can be framed as such a distribution. We obtain an upper bound independent of G for the partition function the normalizing constant which turns the assignment of weights on f V 1 . m into a probability distribution in the case when G is a regular bipartite graph. This generalizes a bound obtained by Galvin and Tetali who considered the simpler weight collection Ai 1 i m u Aj 1 i j m with each Aij either 0 or 1 and with each f chosen with probability proportional to nvev Af v nuveE Af u f v . Our main tools are a generalization to list homomorphisms of a result of Galvin and Tetali on graph homomorphisms and a straightforward second-moment computation. 1 Introduction and statement of results Let G V G E G and H V H E H be non-empty graphs. Set Hom G H f V G V H uv 2 E G f u f v 2 E H that is Hom G H is the set of graph homomorphisms from G to H . In 4 the following result is obtained using entropy considerations and in particular Shearer s Lem ma . This work was begun while the author was a member of the Institute for Advanced Study Einstein Drive Princeton NJ 08540 and was supported in part by NSF grant DMS-0111298. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R72 1 Theorem For any graph H and any d-regular N-vertex bipartite graph G Hom G H Hom Kd d H N where .
