{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T06:33:48Z","timestamp":1768977228353,"version":"3.49.0"},"reference-count":13,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T00:00:00Z","timestamp":1278028800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>Let <jats:italic>I<\/jats:italic> be an independent set drawn from the discrete <jats:italic>d<\/jats:italic>-dimensional hypercube <jats:italic>Q<jats:sub>d<\/jats:sub><\/jats:italic> = {0, 1}<jats:sup><jats:italic>d<\/jats:italic><\/jats:sup> according to the hard-core distribution with parameter \u03bb &gt; 0 (that is, the distribution in which each independent set <jats:italic>I<\/jats:italic> is chosen with probability proportional to \u03bb<jats:sup>|<jats:italic>I<\/jats:italic>|<\/jats:sup>). We show a sharp transition around \u03bb = 1 in the appearance of <jats:italic>I<\/jats:italic>: for \u03bb &gt; 1, min{|<jats:italic>I<\/jats:italic> \u2229 \u0190|, |<jats:italic>I<\/jats:italic> \u2229 <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000155_char1\"\/><\/jats:private-char>|} = 0 asymptotically almost surely, where \u0190 and <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000155_char1\"\/><\/jats:private-char> are the bipartition classes of <jats:italic>Q<jats:sub>d<\/jats:sub><\/jats:italic>, whereas for \u03bb &lt; 1, min{|<jats:italic>I<\/jats:italic> \u2229 \u0190|, |<jats:italic>I<\/jats:italic> \u2229 <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000155_char1\"\/><\/jats:private-char>|} is asymptotically almost surely exponential in <jats:italic>d<\/jats:italic>. The transition occurs in an interval whose length is of order 1\/<jats:italic>d<\/jats:italic>.<\/jats:p><jats:p>A key step in the proof is an estimation of <jats:italic>Z<\/jats:italic><jats:sub>\u03bb<\/jats:sub>(<jats:italic>Q<jats:sub>d<\/jats:sub><\/jats:italic>), the sum over independent sets in <jats:italic>Q<jats:sub>d<\/jats:sub><\/jats:italic> with each set <jats:italic>I<\/jats:italic> given weight \u03bb<jats:sup>|<jats:italic>I<\/jats:italic>|<\/jats:sup> (a.k.a. the hard-core partition function). We obtain the asymptotics of <jats:italic>Z<\/jats:italic><jats:sub>\u03bb<\/jats:sub>(<jats:italic>Q<jats:sub>d<\/jats:sub><\/jats:italic>) for <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000155_inline1\"><jats:alt-text>$\\gl&gt;\\sqrt{2}-1$<\/jats:alt-text><\/jats:inline-graphic>, and nearly matching upper and lower bounds for <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000155_inline2\"><jats:alt-text>$\\gl \\leq \\sqrt{2}-1$<\/jats:alt-text><\/jats:inline-graphic>, 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.<\/jats:p><jats:p>We also derive a long-range influence result. For all fixed \u03bb &gt; 0, if <jats:italic>I<\/jats:italic> is chosen from the independent sets of <jats:italic>Q<jats:sub>d<\/jats:sub><\/jats:italic> according to the hard-core distribution with parameter \u03bb, conditioned on a particular <jats:italic>v<\/jats:italic> \u2208 \u0190 being in <jats:italic>I<\/jats:italic>, then the probability that another vertex <jats:italic>w<\/jats:italic> is in <jats:italic>I<\/jats:italic> is <jats:italic>o<\/jats:italic>(1) for <jats:italic>w<\/jats:italic> \u2208 <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000155_char1\"\/><\/jats:private-char> but \u03a9(1) for <jats:italic>w<\/jats:italic> \u2208 \u0190.<\/jats:p>","DOI":"10.1017\/s0963548310000155","type":"journal-article","created":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T12:00:39Z","timestamp":1278072039000},"page":"27-51","source":"Crossref","is-referenced-by-count":13,"title":["A Threshold Phenomenon for Random Independent Sets in the Discrete Hypercube"],"prefix":"10.1017","volume":"20","author":[{"given":"DAVID","family":"GALVIN","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2010,7,2]]},"reference":[{"key":"S0963548310000155_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02783426"},{"key":"S0963548310000155_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"S0963548310000155_ref9","first-page":"111","article-title":"The number of binary codes with distance 2","volume":"40","author":"Korshunov","year":"1983","journal-title":"Problemy Kibernet."},{"key":"S0963548310000155_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(74)90062-4"},{"key":"S0963548310000155_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20094"},{"key":"S0963548310000155_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"S0963548310000155_ref2","first-page":"605","volume-title":"Proc. Int. Congress of Mathematicians Vol. III","author":"Brightwell","year":"2002"},{"key":"S0963548310000155_ref4","unstructured":"[4] Galvin D. Independent sets of a fixed size in the discrete hypercube. In preparation."},{"key":"S0963548310000155_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548303006035"},{"key":"S0963548310000155_ref7","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"S0963548310000155_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004631"},{"key":"S0963548310000155_ref11","first-page":"42","article-title":"On the number of connected subsets with given cardinality of the boundary in bipartite graphs","volume":"45","author":"Sapozhenko","year":"1987","journal-title":"Metody Diskret. Analiz."},{"key":"S0963548310000155_ref12","first-page":"74","article-title":"The number of antichains in ranked partially ordered sets","volume":"1","author":"Sapozhenko","year":"1989","journal-title":"Diskret. Mat."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548310000155","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T19:57:15Z","timestamp":1556395035000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548310000155\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,2]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["S0963548310000155"],"URL":"https:\/\/doi.org\/10.1017\/s0963548310000155","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7,2]]}}}