Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-23T20:10:22.489Z Has data issue: false hasContentIssue false
  • English
  • Français

An Entropy Approach to the Hard-Core Model on Bipartite Graphs

Published online by Cambridge University Press:  25 June 2001

JEFF KAHN
JEFF KAHN
Affiliation:
Department of Mathematics and RUTCOR, Rutgers University, New Brunswick, NJ 08903, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We use entropy ideas to study hard-core distributions on the independent sets of a finite, regular bipartite graph, specifically distributions according to which each independent set I is chosen with probability proportional to λ[mid ]I[mid ] for some fixed λ > 0. Among the results obtained are rather precise bounds on occupation probabilities; a ‘phase transition’ statement for Hamming cubes; and an exact upper bound on the number of independent sets in an n-regular bipartite graph on a given number of vertices.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 10 , Issue 3 , May 2001 , pp. 219 - 237
Copyright
2001 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)