Duas aplicações da mecânica estatística: percolação em grafos infinitos e lema local de Lovász algorítmico

Abstract

In this work we show a general criterion for bounded degree graphs to exhibit a non-trivial percolation threshold based either on a single isoperimetric inequality if the graph has a biinfinite geodesic, or two isoperimetric inequalities if the graph has not a bi-infinite geodesic. We also study the finite connectivity in graphs satisfying the new general criterion and show that graphs in this class with a bi-infinite geodesicalways have finite connectivity functions with exponential decay when p is suffciently close 1. On the other hand, we show that there are graphs in the same class with no bi-infinite geodesic for which the finite connectivity decays subexponentially (down to polynomially) in the highly supercritical phase even for p arbitrarily close 1. We also point out a close connection between the Moser-Tardos algorithmic version of the Lovász local lemma [59] and the cluster expansion of the hard-core lattice gas in statistical mechanics. We show that the notion of witness trees given by Moser andTardos is essentially coincident with that of Penrose trees in the Cluster expansion scheme of the hard-core gas. Such an identification implies that the Moser-Tardos algorithm is successful in a polynomial time if the cluster expansion converges.