On the stochastic independence properties of hard-core distributions
Tóm tắt
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]).
Tài liệu tham khảo
N. Alon andJ. Spencer:The Probabilistic Method, Wiley, New York, 1992.
J. van den Berg andJ. E. Steif: Percolation and the hard-core lattice gas model,Stochastic Process. Appl.,49 (1994), 179–197.
C. Berge:Hypergraphs: Combinatorics of Finite Sets, North-Holland, Amsterdam, 1989.
B. Bollobás:Extremal Graph Theory, Academic Press, London, 1978.
J. Edmonds: Maximum matching and a polyhedron with 0,1-vertices,J. Res. Nat. Bur. Standards (B),69 (1965), 125–130.
Z. Füredi: Matchings and covers in hypergraphs,Graphs Combin.,4 (1988), 115–206.
C. D. Godsil andI. Gutman: On the theory of the matching polynomial,J. Graph Theory,5 (1981), 137–144.
C. D. Godsil:Algebraic Combinatorics, Chapman and Hall, New York, 1993.
O. J. Heilmann andE. H. Lieb: Monomers and dimers,Phys. Rev. Letters,24 (1970), 1412–1414.
O. J. Heilmann andE. H. Lieb: Theory of monomer-dimer systems,Commun. Math. Phys.,25 (1972), 190–232.
J. Kahn: Asymptotics of the chromatic index for multigraphs,J. Combin. Theory Ser. B,68 (1996), 233–254.
J. Kahn: Asymptotics of the list-chromatic index for multigraphs, submitted.
J. Kahn: A normal law for matchings, submitted.
J. Kahn andP. M. Kayll: Fractional v. integral covers in hypergraphs of bounded edge size,J. Combin. Theory Ser. A,78 (1997), 199–235.
J. Kahn andJ.-H. Kim: Random matchings in regular graphs,Combinatorica, to appear.
P. M. Kayll:Asymptotically Good Covers in Hypergraphs, Dissertation, Rutgers University, New Brunswick, NJ, 1994.
P. M. Kayll: Asymptotically good covers in hypergraphs,Diss. Summ. Math.,1 (1996), 9–16.
P. M. Kayll: “Normal” distributions on matchings in a multigraph: overview with applications,Congr. Numer.,107 (1995), 179–191.
H. Kunz: Location of the zeros of the partition function for some classical lattice systems,Phys. Lett.,32A (1970), 311–312.
C. W. Lee: Some recent results on convex polytopes,Contemporary Mathematics,114 (1990), 3–19.
C. W. Lee: Convex polytopes, the moment map, and canonical convex combinations, manuscript, 1994.
G. M. Louth:Stochastic Networks: Complexity, Dependence and Routing, Dissertation, Cambridge University, 1990.
L. Lovász andM. D. Plummer:Matching Theory, North-Holland, New York, 1986.
J. R. Munkres:Elements of Algebraic Topology, Benjamin/Cummings, Menlo Park, 1984.
Y. Rabinovich, A. Sinclair andA. Wigderson: Quadratic Dynamical Systems (Preliminary Version), in:Proc. 33rd IEEE Symposium on Foundations of Computer Science, pp. 304–313, 1992.
A. Schrijver:Theory of Linear and Integer Programming, Wiley, New York, 1986.
J. Spencer:Ten Lectures on the Probabilistic Method, SIAM, Philadelphia, 1993.