A threshold phenomenon for random independent sets in the discrete hypercube

Details A threshold phenomenon for random independent sets in the discrete hypercube A threshold phenomenon for random independent sets in the discrete hypercube

2008-07-05

arxiv.org/abs/0807.0836v2

Mathematics

Combinatorics

32 pages. To appear in {\em Combinatorics, Probability \& Computing}. This revision corrects minor errors, expands proof of ma

Scientific paper

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^{|I|}$). We show a sharp transition around $\lambda=1$ in the appearance of $I$: for $\lambda>1$, $\min\{|I \cap {\cal E}|, |I \cap {\cal O}|\}=0$ asymptotically almost surely, where ${\cal E}$ and ${\cal O}$ are the bipartition classes of $Q_d$, whereas for $\lambda<1$, $\min\{|I \cap {\cal E}|, |I \cap {\cal O}|\}$ 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^{|I|}$ (a.k.a. the hard-core partition function). We obtain the asymptotics of $Z_\lambda(Q_d)$ for $\lambda>\sqrt{2}-1$, and nearly matching upper and lower bounds for $\lambda \leq \sqrt{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 $v \in {\cal E}$ being in $I$, then the probability that another vertex $w$ is in $I$ is $o(1)$ for $w \in {\cal O}$ but $\Omega(1)$ for $w \in {\cal E}$.

Affiliated with

Also associated with

No associations

Rating

A threshold phenomenon for random independent sets in the discrete hypercube does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A threshold phenomenon for random independent sets in the discrete hypercube, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A threshold phenomenon for random independent sets in the discrete hypercube will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-447879