Den hårdkärniga modellen har under de senaste decennierna fått stor uppmärksamhet som en lattice-gasmodell med hårda begränsningar inom statistisk fysik, en multicast-modell av samtal i kommunikationsnät och som ett viktat självständigt set-problem inom kombinatorik, sannolikhet och teoretisk datavetenskap. I denna modell, varje oberoende uppsättning I i en graf G viktas proportionellt mot λ  för en positiv verklig parameter λ. För stora λ, datorisering partition funktion (nämligen, normalisering konstant som gör viktningen en sannolikhetsfördelning på en ändlig graf) på grafer av maximal grad  på ≥ 3, är en välkänd beräkning utmanande problem. Mer konkret, låt λc(T-) betecknar det kritiska värdet för den så kallade unikhetströskeln för den hårdkärniga modellen på det oändliga vanliga trädet; de senaste genombrottsresultaten från Dror Weitz (2006) och Allan Sly (2010) har identifierat λc(T-) som en tröskel där hårdheten av att uppskatta ovanstående partition funktion genomgår en beräkningsövergång. Vi fokuserar på det välstuderade speciella fallet av torget lattice Z 2, och ger en ny lägre gräns för unikhetströskeln, särskilt att ta det väl över λc(T4). Vår teknik förfinar och bygger på trädet av självundvikande promenader tillvägagångssätt av Weitz, vilket resulterar i en ny teknisk tillräcklig kriterium (av bredare tillämplighet) för att etablera stark rumslig blandning (och därmed unikhet) för den hårda-kärnan modellen. Vårt nya kriterium uppnår bättre gränser för stark rumslig blandning när grafen har extra struktur, förbättra vad som kan uppnås genom att bara använda den maximala graden. Genom att tillämpa vår teknik på Z 2 visar vi att stark rumslig blandning håller för alla λ < 2.3882, förbättra arbetet i Weitz som höll för λ < 27/16 = 1.6875. Våra resultat innebär en helt-polynomiell deterministisk approximationsalgoritm för uppskattning av partitionsfunktionen, samt en snabb blandning av den tillhörande Glauberdynamiken för att ta prov från den hårdkärniga distributionen.
Å andra sidan, i specialfallet av den hårda kärnmodellen på den tvådimensionella Cartesian lattice Z 2, Restrepo, Shin, Tetali, Vigoda och Yang REF förbättrades på tröskeln för stark rumslig blandning som erhållits med hjälp av en direkt tillämpning av Weitz resultat.
Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets
{'venue': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'journal': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science', 'Mathematics']}