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

Jeffry Kahn

doi:10.1017/S0963548301004631

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

Jeffry Kahn

SAS - Mathematics

Research output: Contribution to journal › Article › peer-review

87 Scopus citations

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 λ^|I| 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.

Original language	English (US)
Pages (from-to)	219-237
Number of pages	19
Journal	Combinatorics Probability and Computing
Volume	10
Issue number	3
DOIs	https://doi.org/10.1017/S0963548301004631
State	Published - Dec 1 2001

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Statistics and Probability
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1017/S0963548301004631

Fingerprint Dive into the research topics of 'An Entropy Approach to the Hard-Core Model on Bipartite Graphs'. Together they form a unique fingerprint.

Cite this

@article{deb94bfde2eb483981003daf38ef0b75,

title = "An Entropy Approach to the Hard-Core Model on Bipartite Graphs",

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 λ|I| 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.",

author = "Jeffry Kahn",

year = "2001",

month = dec,

day = "1",

doi = "10.1017/S0963548301004631",

language = "English (US)",

volume = "10",

pages = "219--237",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "3",

}

TY - JOUR

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

AU - Kahn, Jeffry

PY - 2001/12/1

Y1 - 2001/12/1

N2 - 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 λ|I| 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.

AB - 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 λ|I| 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.

UR - http://www.scopus.com/inward/record.url?scp=0035626591&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035626591&partnerID=8YFLogxK

U2 - 10.1017/S0963548301004631

DO - 10.1017/S0963548301004631

M3 - Article

AN - SCOPUS:0035626591

VL - 10

SP - 219

EP - 237

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

SN - 0963-5483

IS - 3

ER -