A Threshold Phenomenon for Random Independent Sets in the Discrete Hypercube

Let I be an independent set drawn from the discrete d-dimensional hypercube Q(d) = {0, 1}(d) according to the hard-core distribution with parameter lambda > 0 (that is, the distribution in which each independent set I is chosen with probability proportional to lambda(vertical bar I vertical bar)). We show a sharp transition around lambda = 1 in the appearance of I: for lambda > 1, min{vertical bar I boolean AND epsilon vertical bar, vertical bar I boolean AND O vertical bar} = 0 asymptotically almost surely, where epsilon and O are the bipartition classes of Q(d), whereas for lambda < 1, min{vertical bar I boolean AND epsilon vertical bar, vertical bar I boolean AND O vertical bar} is asymptotically almost surely exponential in d. The transition occurs in an interval whose length is of order 1/d. A key step in the proof is an estimation of Z(lambda)(Q(d)), the sum over independent sets in Q(d) with each set I given weight lambda(vertical bar I vertical bar) (a.k.a. the hard-core partition function). We obtain the asymptotics of Z(lambda)(Q(d)) for lambda > root 2 - 1, and nearly matching upper and lower bounds for lambda <= root 2 - 1, extending work of Korshunov and Sapozhenko. These bounds allow us to read off some very specific information about the structure of an independent set drawn according to the hard-core distribution. We also derive a long-range influence result. For all fixed lambda > 0, if I is chosen from the independent sets of Q(d) according to the hard-core distribution with parameter lambda, conditioned on a particular nu epsilon epsilon being in I, then the probability that another vertex w is in I is o(1) for w epsilon O but Omega(1) for w epsilon epsilon.