On the stochastic independence properties of hard-core distributions
type: Item
instance of: scholarly article
title: On the stochastic independence properties of hard-core distributions
zbMATH Open document ID: 0902.05055
DOI: 10.1007/BF01215919
author: P. Mark Kayll
author: J. Kahn
published in: Combinatorica
publication date: 1998-11-23T00:00:00Z
review text: A probability measure \(p\) on the set \({\mathcal M}\) of matchings in a graph (or, more generally 2-bounded hypergraph) \(\Gamma\) is hard-core if for some \(\lambda :\Gamma\mapsto [0,\infty)\), the probability \(p(M)\) of \(M\in{\mathcal M}\) is proportional to \(\prod _{A\in M}\lambda (A)\). It is shown in this paper that such distributions have substantial approximate stochastic independence properties, e.g. the main theorem is: For every \(\delta \in (0,1)\), \(\eta >0\) and \(\ell\geq 1\), there exist \(\varepsilon >0\) and an integer \(D\) such that the following is true. Let \(\Gamma\) be a multigraph and \({\mathcal M}\) the set of matchings in \(\Gamma\). Let \(p\) be a hard-core distribution on \({\mathcal M}\) with marginals \(f_p\in (1-\delta)\text{MP}(\Gamma)\) (here MP\((\Gamma)\) is the matching polytope of \(\Gamma\)), and let \(\Gamma ' =\{A\in\Gamma :p_A>\varepsilon\}\). If \(F_1,\dots F_\ell\in\Gamma\) are pairwise at distance at least \(D\) in \(\Gamma '\), then Pr\((F_1,\dots F_\ell\in M)=\eta\prod_{i=1}^\ell p_{F_i}\). This result is obtained through a sequence of lemmata which are interesting at their own, too. The obtained results are very useful in the resolution of several questions involving the asymptotic behaviour of graphs and hypergraphs.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 52B12
Mathematics Subject Classification ID: 82B20
zbMATH DE Number: 1226325
zbMATH Keywords: graph
zbMATH Keywords: hypergraph
zbMATH Keywords: stochastic independence
zbMATH Keywords: hard-core distribution
zbMATH Keywords: matching polytope
zbMATH Keywords: marginals
MaRDI profile type: Publication
cites work: Percolation and the hard-core lattice gas model
cites work: Q3993087
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Matchings and covers in hypergraphs
cites work: On the theory of the matching polynomial
cites work: Theory of monomer-dimer systems
cites work: Asymptotics of the chromatic index for multigraphs
cites work: Q4511485
cites work: A normal law for matchings
cites work: Fractional v. integral covers in hypergraphs of bounded edge size
cites work: Q4386088
cites work: Q4230353
cites work: Q3818127
cites work: Q4326389
description: scientific article; zbMATH DE number 1226325