ISSN:
1439-6912
Keywords:
05C70
;
05C65
;
60C05
;
52B12
;
82B20
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract A probability measurep on the set μ of matchings in a graph (or, more generally 2-bounded hypergraph) Γ ishard-core if for some λ: Γ→[0,∞), the probabilityp(M) ofM∈μ is proportional to $$\prod\nolimits_{A_ \in M} {\lambda (A)}$$ . We show that such distributions enjoy substantial approximate stochastic independence properties. This is based on showing that, withM chosen according to the hard-core distributionp, MP (Γ) the matching polytope of Γ, and σ〉0, if the vector ofmarginals, (Pr(A∈M):A an edge of Γ), is in (1−σ) MP (Γ), then the weights λ(A) are bounded by someA(σ). This eventually implies, for example, that under the same assumption, with σ fixed, $$\frac{{\Pr (A,B \in M)}}{{\Pr (A \in M)\Pr (B \in M)}} \to 1$$ as the distance betweenA, 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]).
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01215919
Permalink
