On the stochastic independence properties of hard-core distributions

Jeffry Kahn, P. Mark Kayll

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

A probability measure p on the set M of matchings in a graph (or, more generally 2-bounded hypergraph) Γ is hard-core if for some λ:Γ → [0, ∞), the probability p(M) of M ∈ M is proportional to ΠA∈M λ(A). We show that such distributions enjoy substantial approximate stochastic independence properties. This is based on showing that, with M chosen according to the hard-core distribution p, MP (Γ) the matching polytope of Γ, and δ > 0, if the vector of marginals, (Pr(A ∈ M): A an edge of Γ), is in (1 - δ)MP (Γ), then the weights λ(A) are bounded by some A(δ). This eventually implies, for example, that under the same assumption, with δ fixed, Pr(A,B∈M)/Pr(A∈M)Pr(B∈M) → 1 as the distance between A, B ∈ Γ tends to infinity. Thought to be of independent interest, our results have already been applied in the resolutions of several questions involving asymptotic behaviour of graphs and hypergraphs (see [14, 16], [11]-[13]).

Original languageEnglish (US)
Pages (from-to)369-391
Number of pages23
JournalCombinatorica
Volume17
Issue number3
DOIs
StatePublished - Jan 1 1997

Fingerprint

Hypergraph
Graph in graph theory
Polytope
Probability Measure
Asymptotic Behavior
Directly proportional
Infinity
Tend
Imply
Independence

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Cite this

Kahn, Jeffry ; Kayll, P. Mark. / On the stochastic independence properties of hard-core distributions. In: Combinatorica. 1997 ; Vol. 17, No. 3. pp. 369-391.
@article{9e8e59d2312b429e8f492e8be60b8308,
title = "On the stochastic independence properties of hard-core distributions",
abstract = "A probability measure p on the set M of matchings in a graph (or, more generally 2-bounded hypergraph) Γ is hard-core if for some λ:Γ → [0, ∞), the probability p(M) of M ∈ M is proportional to ΠA∈M λ(A). We show that such distributions enjoy substantial approximate stochastic independence properties. This is based on showing that, with M chosen according to the hard-core distribution p, MP (Γ) the matching polytope of Γ, and δ > 0, if the vector of marginals, (Pr(A ∈ M): A an edge of Γ), is in (1 - δ)MP (Γ), then the weights λ(A) are bounded by some A(δ). This eventually implies, for example, that under the same assumption, with δ fixed, Pr(A,B∈M)/Pr(A∈M)Pr(B∈M) → 1 as the distance between A, B ∈ Γ tends to infinity. Thought to be of independent interest, our results have already been applied in the resolutions of several questions involving asymptotic behaviour of graphs and hypergraphs (see [14, 16], [11]-[13]).",
author = "Jeffry Kahn and Kayll, {P. Mark}",
year = "1997",
month = "1",
day = "1",
doi = "10.1007/BF01215919",
language = "English (US)",
volume = "17",
pages = "369--391",
journal = "Combinatorica",
issn = "0209-9683",
publisher = "Janos Bolyai Mathematical Society",
number = "3",

}

On the stochastic independence properties of hard-core distributions. / Kahn, Jeffry; Kayll, P. Mark.

In: Combinatorica, Vol. 17, No. 3, 01.01.1997, p. 369-391.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the stochastic independence properties of hard-core distributions

AU - Kahn, Jeffry

AU - Kayll, P. Mark

PY - 1997/1/1

Y1 - 1997/1/1

N2 - A probability measure p on the set M of matchings in a graph (or, more generally 2-bounded hypergraph) Γ is hard-core if for some λ:Γ → [0, ∞), the probability p(M) of M ∈ M is proportional to ΠA∈M λ(A). We show that such distributions enjoy substantial approximate stochastic independence properties. This is based on showing that, with M chosen according to the hard-core distribution p, MP (Γ) the matching polytope of Γ, and δ > 0, if the vector of marginals, (Pr(A ∈ M): A an edge of Γ), is in (1 - δ)MP (Γ), then the weights λ(A) are bounded by some A(δ). This eventually implies, for example, that under the same assumption, with δ fixed, Pr(A,B∈M)/Pr(A∈M)Pr(B∈M) → 1 as the distance between A, B ∈ Γ tends to infinity. Thought to be of independent interest, our results have already been applied in the resolutions of several questions involving asymptotic behaviour of graphs and hypergraphs (see [14, 16], [11]-[13]).

AB - A probability measure p on the set M of matchings in a graph (or, more generally 2-bounded hypergraph) Γ is hard-core if for some λ:Γ → [0, ∞), the probability p(M) of M ∈ M is proportional to ΠA∈M λ(A). We show that such distributions enjoy substantial approximate stochastic independence properties. This is based on showing that, with M chosen according to the hard-core distribution p, MP (Γ) the matching polytope of Γ, and δ > 0, if the vector of marginals, (Pr(A ∈ M): A an edge of Γ), is in (1 - δ)MP (Γ), then the weights λ(A) are bounded by some A(δ). This eventually implies, for example, that under the same assumption, with δ fixed, Pr(A,B∈M)/Pr(A∈M)Pr(B∈M) → 1 as the distance between A, B ∈ Γ tends to infinity. Thought to be of independent interest, our results have already been applied in the resolutions of several questions involving asymptotic behaviour of graphs and hypergraphs (see [14, 16], [11]-[13]).

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

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

U2 - 10.1007/BF01215919

DO - 10.1007/BF01215919

M3 - Article

VL - 17

SP - 369

EP - 391

JO - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 3

ER -