Counting independent sets in percolated graphs via the Ising model

Anna Geisler; Michail Sarantis; Mihyun Kang; Ronen Wdowinski

arxiv: 2504.08715 · v2 · pith:MEZE2QGRnew · submitted 2025-04-11 · 🧮 math.CO

Counting independent sets in percolated graphs via the Ising model

Anna Geisler , Mihyun Kang , Michail Sarantis , Ronen Wdowinski This is my paper

Pith reviewed 2026-05-22 20:02 UTC · model grok-4.3

classification 🧮 math.CO

keywords independent setspercolationIsing modelcluster expansiongraph containersbipartite graphsrandom subgraphsasymptotic expansion

0 comments

The pith

The expected number of independent sets in percolated regular bipartite graphs admits an asymptotic expansion derived from the Ising model.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper shows how to obtain an asymptotic expansion for the expected number of independent sets in random subgraphs of regular bipartite graphs that meet specific vertex-isoperimetric conditions. The work builds on earlier results for the hypercube by using a combination of graph container techniques and cluster expansions from the Ising model in statistical physics. The expansion applies when the parameters are in a suitable range for the cluster expansion to be valid. Applications include results for even tori with increasing dimensions, and the paper also presents a refined container lemma for the Ising model that slightly improves prior bounds.

Core claim

The authors establish an asymptotic expansion for the expected number of independent sets in the p-percolated version of regular bipartite graphs satisfying vertex-isoperimetric properties. This is achieved by expressing the expectation in terms of the partition function of the Ising model and then applying a cluster expansion after using a refined graph container lemma to control the contributions.

What carries the argument

The refined container lemma for the Ising model combined with cluster expansion, which provides improved bounds allowing an asymptotic series for the partition function in the relevant parameter regime.

If this is right

Even tori of growing side length have an asymptotic expansion for the expected independent set count in their percolated subgraphs.
The method applies to any regular bipartite graph with the given isoperimetric properties.
The partition function of the Ising model admits an expansion via containers and cluster methods in this setting.
Independent set counts in random subgraphs can be approximated using these expansions for large graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar techniques might apply to counting other structures like matchings in percolated graphs.
This connects independent set enumeration to percolation theory and phase transitions in Ising models.
For practical computation, the expansion could be truncated for numerical estimates in large networks.

Load-bearing premise

The underlying graphs must satisfy the vertex-isoperimetric properties and the Ising model parameters must lie in the range where the cluster expansion is valid.

What would settle it

Direct computation of the expected number of independent sets for a small even torus and comparison against the first few terms of the claimed asymptotic expansion.

read the original abstract

Given a graph $G$, we form a random subgraph $G_p$ by including each edge of $G$ independently with probability $p$. We provide an asymptotic expansion of the expected number of independent sets in random subgraphs of regular bipartite graphs satisfying certain vertex-isoperimetric properties, extending the work of Kronenberg and Spinka on the percolated hypercube. Combining graph containers with the cluster expansion from statistical physics, we give an expansion of the partition function of the Ising model in certain range of the parameters. Among other applications, we obtain results for even tori of growing side-length. As a tool, we prove a refined container lemma for the Ising model, which mildly improves recent bounds of Jenssen, Malekshahian, and Park.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Extends the percolated hypercube independent-set expansion to regular bipartite graphs with vertex-isoperimetric properties via Ising cluster expansion and a refined container lemma.

read the letter

The main point here is a direct extension of Kronenberg and Spinka's asymptotic for the expected number of independent sets in the percolated hypercube. The authors carry the same Ising-model plus cluster-expansion approach over to regular bipartite graphs that satisfy vertex-isoperimetric conditions, and they obtain concrete results for even tori of growing side length. As a side tool they prove a refined container lemma for the Ising model that improves the recent bounds of Jenssen, Malekshahian, and Park by a modest amount. The combination is handled cleanly and the new lemma looks like a small but reusable technical step. The work is honest progress inside combinatorial enumeration; nothing reorganizes the field, but the extension is non-routine and the applications are explicit. The soft spot is the justification for cluster-expansion convergence. The abstract limits the claim to a certain parameter range and invokes the isoperimetric properties for both the container lemma and the needed decay of connected clusters. It is not immediately obvious whether those properties alone produce a uniform bound on the radius of convergence that holds as p varies and the fugacity is fixed to count independent sets. If the paper derives an explicit p-interval or graph-dependent constant from the isoperimetric hypothesis, the argument is fine; otherwise that step needs a close check. This paper is for people who already work with container methods or cluster expansions on graphs. A reader who wants to see the technique applied beyond the hypercube or who needs the improved container lemma will get something concrete out of it. The formal grounding and the explicit applications are strong enough that it deserves a serious referee rather than a desk rejection.

Referee Report

2 major / 2 minor

Summary. The paper claims an asymptotic expansion for the expected number of independent sets in the random subgraph G_p of regular bipartite graphs satisfying vertex-isoperimetric properties. The expansion is obtained by mapping the problem to the Ising partition function and applying cluster expansion techniques, extending Kronenberg-Spinka results on the percolated hypercube; a refined container lemma for the Ising model is proved as a tool, with applications including even tori of growing side length.

Significance. If the error-term control and parameter regime are fully established, the result would broaden the scope of cluster-expansion methods for counting independent sets beyond the hypercube to a natural class of bipartite graphs, while the refined container lemma mildly strengthens recent bounds in the literature.

major comments (2)

[Abstract and cluster-expansion section] The central claim requires that vertex-isoperimetric properties imply the uniform radius of convergence and exponential decay of connected clusters needed for the cluster expansion when p varies and the fugacity is chosen to count independent sets. The abstract invokes these properties to justify both the container lemma and the expansion, but the derivation of an explicit p-interval or graph-dependent constant from the isoperimetric hypothesis is not visible; this is load-bearing for the asymptotic expansion asserted in the abstract.
[Container-lemma section] The refined container lemma is presented as a tool that mildly improves Jenssen-Malekshahian-Park bounds; however, the precise improvement (e.g., the dependence on the isoperimetric constant or on the Ising parameters) must be stated explicitly to confirm it is sufficient for the subsequent cluster-expansion error control.

minor comments (2)

Notation for the effective field and fugacity parameters should be introduced once and used consistently when transitioning from the independent-set count to the Ising model.
The statement of the vertex-isoperimetric assumption should include the precise constants that enter the error bounds, rather than remaining at the level of 'certain properties.'

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and indicate the revisions we will make to strengthen the presentation.

read point-by-point responses

Referee: [Abstract and cluster-expansion section] The central claim requires that vertex-isoperimetric properties imply the uniform radius of convergence and exponential decay of connected clusters needed for the cluster expansion when p varies and the fugacity is chosen to count independent sets. The abstract invokes these properties to justify both the container lemma and the expansion, but the derivation of an explicit p-interval or graph-dependent constant from the isoperimetric hypothesis is not visible; this is load-bearing for the asymptotic expansion asserted in the abstract.

Authors: We agree that an explicit derivation of the admissible p-interval from the vertex-isoperimetric constant would improve clarity. In the current manuscript, the radius of convergence is controlled in Section 3 via a direct application of the isoperimetric inequality to bound the weights of connected clusters (see the proof of Theorem 3.2 and the subsequent corollary on exponential decay). To make this load-bearing step fully transparent, we will add an explicit statement (as a new corollary) that extracts a concrete interval for p in terms of the isoperimetric constant and the maximum degree; this will also be referenced from the abstract. revision: yes
Referee: [Container-lemma section] The refined container lemma is presented as a tool that mildly improves Jenssen-Malekshahian-Park bounds; however, the precise improvement (e.g., the dependence on the isoperimetric constant or on the Ising parameters) must be stated explicitly to confirm it is sufficient for the subsequent cluster-expansion error control.

Authors: We concur that the precise nature of the improvement should be stated more explicitly. The refined container lemma (Theorem 4.1) improves the dependence on the isoperimetric constant in the error term relative to Jenssen-Malekshahian-Park by incorporating a tighter bound on the number of containers that exploits the bipartite structure and the specific range of the Ising parameters. In the revision we will insert a dedicated remark immediately after the statement of the lemma that quantifies this improvement (including the explicit dependence on the isoperimetric constant) and explains why the resulting error is sufficient to close the cluster-expansion argument in Section 5. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation combines external cluster expansion and container methods

full rationale

The paper maps independent-set counting in percolated regular bipartite graphs to the Ising partition function and applies cluster expansion plus a refined container lemma. Both the cluster-expansion technique and the base container bounds are drawn from the statistical-physics and combinatorics literature (Kronenberg-Spinka, Jenssen-Malekshahian-Park). The vertex-isoperimetric hypothesis is an explicit assumption that delimits the parameter regime; it is not derived from the target expansion. No equation or claim reduces by construction to a quantity fitted or defined inside the paper, and no load-bearing step rests on a self-citation chain. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review prevents identification of concrete free parameters or invented entities; the work rests on the standard domain assumption that cluster expansion converges for the relevant Ising parameters on the stated graphs.

axioms (1)

domain assumption Cluster expansion converges for the Ising model on the graphs under consideration when parameters lie in the stated range.
Invoked to obtain the expansion of the partition function from the abstract.

pith-pipeline@v0.9.0 · 5660 in / 1183 out tokens · 60325 ms · 2026-05-22T20:02:21.731098+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We provide an asymptotic expansion of the expected number of independent sets in random subgraphs of regular bipartite graphs satisfying certain vertex-isoperimetric properties, extending the work of Kronenberg and Spinka on the percolated hypercube. Combining graph containers with the cluster expansion from statistical physics...

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

63 extracted references · 63 canonical work pages · 2 internal anchors

[1]

Ajtai, J

M. Ajtai, J. Koml´ os, and E. Szemer´ edi. Largest random c omponent of a k-cube. Combinatorica, 2:1–7, 1982

work page 1982
[2]

Alon and J

N. Alon and J. H. Spencer. The Probabilistic Method . John Wiley & Sons, 2016

work page 2016
[3]

Balogh, R

J. Balogh, R. Morris, and W. Samotij. The method of hyperg raph containers. In Proceedings of the Inter- national Congress of Mathematicians (ICM 2018) , pages 3059–3092. World Scientiﬁc, 2019

work page 2018
[4]

Balogh, D

J. Balogh, D. Dong, B. Lidick´ y, N. Mani, and Y. Zhao. Near ly all k-SAT functions are unate. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , STOC ’23, pages 958–962. ACM, 2023. 35

work page 2023
[5]

Balogh, R

J. Balogh, R. I. Garcia, and L. Li. Independent sets in the middle two layers of Boolean lattice. Journal of Combinatorial Theory, Series A , 178:105341, 2021

work page 2021
[6]

Balogh and R

J. Balogh and R. A. Krueger. A sharp threshold for a random version of Sperner’s theorem. Random Structures & Algorithms , 66(1):e21259, 2025

work page 2025
[7]

Balogh, B

J. Balogh, B. Narayanan, and J. Skokan. The number of hype rgraphs without linear cycles. Journal of Combinatorial Theory, Series B , 134:309–321, 2019

work page 2019
[8]

Bez´ akov´ a, A

I. Bez´ akov´ a, A. Galanis, L. A. Goldberg, and D. ˇStefankoviˇ c. Fast sampling via spectral independence beyond bounded-degree graphs. ACM Transactions on Algorithms , 20(1):1–26, 2024

work page 2024
[9]

Bez´ akov´ a, A

I. Bez´ akov´ a, A. Galanis, L. A. Goldberg, and D. ˇStefankoviˇ c. Inapproximability of the independent set polynomial in the complex plane. In Proceedings of the 50th annual ACM SIGACT symposium on theor y of computing , pages 1234–1240, 2018

work page 2018
[10]

Bollob´ as

B. Bollob´ as. The evolution of the cube. In North-Holland Mathematics Studies . Volume 75, pages 91–97. Elsevier, 1983

work page 1983
[11]

Bollob´ as, Y

B. Bollob´ as, Y. Kohayakawa, and T. /suppress Luczak. The evolution of random subgraphs of the cube. Random Structures & Algorithms , 1992

work page 1992
[12]

Bollob´ as and O

B. Bollob´ as and O. Riordan. Percolation. Cambridge University Press, UK, 2006

work page 2006
[13]

Campos and W

M. Campos and W. Samotij. Towards an optimal hypergraph container lemma. arXiv:2408.06617 preprint, 2024

work page arXiv 2024
[14]

M. B. R. Chowdhury, S. Ganguly, and V. Winstein. Gaussia n to log-normal transition for independent sets in a percolated hypercube. arXiv:2410.07080 preprint , 2024

work page arXiv 2024
[15]

Coja-Oghlan and C

A. Coja-Oghlan and C. Efthymiou. On independent sets in random graphs. Random Structures & Algo- rithms, 47(3):436–486, 2015

work page 2015
[16]

Collares, J

M. Collares, J. Erde, A. Geisler, and M. Kang. Counting i ndependent sets in expanding bipartite regular graphs. arXiv:2503.22255 preprint , 2025

work page arXiv 2025
[17]

Davies, M

E. Davies, M. Jenssen, and W. Perkins. A proof of the uppe r matching conjecture for large graphs. Journal of Combinatorial Theory, Series B , 151:393–416, 2021

work page 2021
[18]

R. L. Dobrushin. Estimates of semi-invariants for the I sing model at low temperatures. Translations of the American Mathematical Society-Series 2 , 177:59–82, 1996

work page 1996
[19]

J. Erde, M. Kang, and M. Krivelevich. Expansion in super critical random subgraphs of the hypercube and its consequences. The Annals of Probability , 51(1):127–156, 2023

work page 2023
[20]

Erd˝ os and J

P. Erd˝ os and J. Spencer. Evolution of the n-cube. Computers & Mathematics with Applications , 5(1):33–39, 1979

work page 1979
[21]

A. M. Frieze. On the independence number of random graph s. Discrete Mathematics, 81(2):171–175, 1990

work page 1990
[22]

D. Galvin. A threshold phenomenon for random independe nt sets in the discrete hypercube. Combinatorics, probability and computing , 20(1):27–51, 2011

work page 2011
[23]

D. Galvin. Independent sets in the discrete hypercube. arXiv:1901.01991 preprint , 2019

work page internal anchor Pith review Pith/arXiv arXiv 1901
[24]

Galvin and J

D. Galvin and J. Kahn. On phase transition in the hard-co re model on Zd. Combinatorics, Probability and Computing, 13(2):137–164, 2004

work page 2004
[25]

Galvin and P

D. Galvin and P. Tetali. On weighted graph homomorphism s. DIMACS Series in Discrete Mathematics and Theoretical Computer Science , 63:97–104, 2004

work page 2004
[26]

Galvin and P

D. Galvin and P. Tetali. Slow mixing of Glauber dynamics for the hard-core model on regular bipartite graphs. Random Structures & Algorithms , 28(4):427–443, 2006

work page 2006
[27]

D. J. Galvin. Bounding the partition function of spin-s ystems. The Electronic Journal of Combinatorics :R72– R72, 2006

work page 2006
[28]

G. R. Grimmett. Percolation. Springer, Berlin, 1999

work page 1999
[29]

Hulshof and A

T. Hulshof and A. Nachmias. Slightly subcritical hyper cube percolation. Random Structures & Algorithms , 56(2):557–593, 2020

work page 2020
[30]

M. Jenssen. Personal communication, 2025

work page 2025
[31]

Jenssen and P

M. Jenssen and P. Keevash. Homomorphisms from the torus . Advances in Mathematics , 430:109212, 2023

work page 2023
[32]

Jenssen, A

M. Jenssen, A. Malekshahian, and J. Park. A reﬁned graph container lemma and applications to the hard-core model on bipartite expanders. arXiv:2411.03393 preprint, 2024

work page arXiv 2024
[33]

Jenssen, A

M. Jenssen, A. Malekshahian, and J. Park. On Dedekind’s problem, a sparse version of Sperner’s theorem, and antichains of a given size in the Boolean lattice. arXiv:2411.03400 preprint, 2024

work page arXiv 2024
[34]

Jenssen and W

M. Jenssen and W. Perkins. Independent sets in the hyper cube revisited. Journal of the London Mathe- matical Society, 102(2):645–669, 2020

work page 2020
[35]

Jenssen, W

M. Jenssen, W. Perkins, and A. Potukuchi. Approximatel y counting independent sets in bipartite graphs via graph containers. Random Structures & Algorithms , 63(1):215–241, 2023

work page 2023
[36]

Jenssen, W

M. Jenssen, W. Perkins, and A. Potukuchi. Independent s ets of a given size and structure in the hypercube. Combinatorics, Probability and Computing , 31(4):702–720, 2022

work page 2022
[37]

Jenssen, W

M. Jenssen, W. Perkins, and A. Potukuchi. On the evoluti on of structure in triangle-free graphs. arXiv:2312.09202 preprint, 2023. 36

work page arXiv 2023
[38]

Jenssen, W

M. Jenssen, W. Perkins, A. Potukuchi, and M. Simkin. Sam pling and counting triangle-free graphs near the critical density. Foundations of Computer Science , 2024

work page 2024
[39]

J. Kahn. An entropy approach to the hard-core model on bi partite graphs. Combinatorics, Probability and Computing, 10(3):219–237, 2001

work page 2001
[40]

Kahn and J

J. Kahn and J. Park. The number of maximal independent se ts in the Hamming cube. Combinatorica, 42(6):853–880, 2022

work page 2022
[41]

G. Katona. A theorem of ﬁnite sets . In Classic Papers in Combinatorics . Birkh¨ auser Boston, 2009, pages 381– 401

work page 2009
[42]

Korshunov and A

A. Korshunov and A. Sapozhenko. The number of binary cod es with distance 2. In Russian. Problemy Kibernet, 40:111–130, 1983

work page 1983
[43]

Koteck´ y and D

R. Koteck´ y and D. Preiss. Cluster expansion for abstra ct polymer models. Communications in Mathematical Physics, 103:491–498, 1986

work page 1986
[44]

Krivelevich, T

M. Krivelevich, T. M´ esz´ aros, P. Michaeli, and C. Shik helman. Greedy maximal independent sets via local limits. Random Structures & Algorithms , 64(4):986–1015, 2024

work page 2024
[45]

Krivelevich, B

M. Krivelevich, B. Sudakov, V. H. Vu, and N. C. Wormald. O n the probability of independent sets in random graphs. Random Structures & Algorithms , 22(1):1–14, 2003

work page 2003
[46]

Kronenberg and Y

G. Kronenberg and Y. Spinka. Independent sets in random subgraphs of the hypercube. arXiv:2201.06127 preprint, 2022

work page arXiv 2022
[47]

J. B. Kruskal. The number of simplices in a complex . In Mathematical Optimization Techniques. University of California Press, 1963, pages 251–278

work page 1963
[48]

L. Li, G. McKinley, and J. Park. The number of colorings o f the middle layers of the Hamming cube. Combinatorica, 2025

work page 2025
[49]

Mattheus, D

S. Mattheus, D. Mubayi, J. Nie, and J. Verstra¨ ete. Oﬀ-d iagonal Ramsey numbers for slowly growing hypergraphs. Random Structures and Algorithms , 66(1):Paper No. e21284, 2025

work page 2025
[50]

Mubayi and L

D. Mubayi and L. Yepremyan. Random Tur´ an theorem for hy pergraph cycles. arXiv:2304.15003 preprint , 2023

work page arXiv 2023
[51]

R. Nenadov. Probabilistic hypergraph containers. Israel Journal of Mathematics , 261(2):879–897, 2023

work page 2023
[52]

Nenadov and H

R. Nenadov and H. T. Pham. Short proof of the hypergraph c ontainer theorem. Combinatorics, Probability & Computing , 2025

work page 2025
[53]

Nenadov and L

R. Nenadov and L. Verlinde. Containers with non-unifor m co-degree conditions, and an application to nearly orthogonal sets. arXiv:2411.07549 preprint , 2024

work page arXiv 2024
[54]

Nikoletseas, C

S. Nikoletseas, C. Raptopoulos, and P. Spirakis. Large independent sets in general random intersection graphs. Theoretical Computer Science , 406(3):215–224, 2008

work page 2008
[55]

J. Park. Note on the number of balanced independent sets in the Hamming cube. The Electronic Journal of Combinatorics :P2–34, 2022

work page 2022
[56]

Long-range order in discrete spin systems

R. Peled and Y. Spinka. Long-range order in discrete spi n systems. arXiv:2010.03177 preprint, 2024

work page internal anchor Pith review Pith/arXiv arXiv 2010
[57]

Potukuchi and L

A. Potukuchi and L. Yepremyan. Enumerating independen t sets in Abelian Cayley graphs. arXiv:2109.06152 preprint, 2021

work page arXiv 2021
[58]

A. A. Sapozhenko. On the number of antichains in multile velled ranked posets. Discrete Mathematics and Applications, 1(2), 1991

work page 1991
[59]

Saxton and A

D. Saxton and A. Thomason. Hypergraph containers. Inventiones mathematicae , 201(3):925–992, 2015

work page 2015
[60]

Sly and N

A. Sly and N. Sun. Counting in two-spin models on d-regul ar graphs. The Annals of Probability , 42(6):2383– 2416, 2014

work page 2014
[61]

van der Hofstad and A

R. van der Hofstad and A. Nachmias. Hypercube percolati on. Journal of the European Mathematical Society, 19(3):725–814, 2017

work page 2017
[62]

D. Weitz. Counting independent sets up to the tree thres hold. In Proceedings of the thirty-eighth annual ACM Symposium on Theory of Computing , pages 140–149, 2006. 37 Appendix A. Weights of vertex sets via partition functions and entropy In this appendix, we detail some of the main ingredients that go into bounding weights of large polymers as well as t...

work page 2006
[63]

orα ≥ C′ 0 log3/ 2d d1− C5/ 2 (if 1 ≤ C5< 2). These lower bounds on α hold because, when d is suﬃciently large, λ ≥ C0 log3/ 2d d1/ 2 implies that α = log(1 + λ) ≥ C0 log3/ 2d 2d1/ 2 , and likewise λ ≥ C0 log3/ 2d d1− C5/ 2 implies that α = log(1 + λ) ≥ C0 log3/ 2d 2d1− C5/ 2 . And as we mentioned above, the last term of the exponential also dominates the...

work page

[1] [1]

Ajtai, J

M. Ajtai, J. Koml´ os, and E. Szemer´ edi. Largest random c omponent of a k-cube. Combinatorica, 2:1–7, 1982

work page 1982

[2] [2]

Alon and J

N. Alon and J. H. Spencer. The Probabilistic Method . John Wiley & Sons, 2016

work page 2016

[3] [3]

Balogh, R

J. Balogh, R. Morris, and W. Samotij. The method of hyperg raph containers. In Proceedings of the Inter- national Congress of Mathematicians (ICM 2018) , pages 3059–3092. World Scientiﬁc, 2019

work page 2018

[4] [4]

Balogh, D

J. Balogh, D. Dong, B. Lidick´ y, N. Mani, and Y. Zhao. Near ly all k-SAT functions are unate. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , STOC ’23, pages 958–962. ACM, 2023. 35

work page 2023

[5] [5]

Balogh, R

J. Balogh, R. I. Garcia, and L. Li. Independent sets in the middle two layers of Boolean lattice. Journal of Combinatorial Theory, Series A , 178:105341, 2021

work page 2021

[6] [6]

Balogh and R

J. Balogh and R. A. Krueger. A sharp threshold for a random version of Sperner’s theorem. Random Structures & Algorithms , 66(1):e21259, 2025

work page 2025

[7] [7]

Balogh, B

J. Balogh, B. Narayanan, and J. Skokan. The number of hype rgraphs without linear cycles. Journal of Combinatorial Theory, Series B , 134:309–321, 2019

work page 2019

[8] [8]

Bez´ akov´ a, A

I. Bez´ akov´ a, A. Galanis, L. A. Goldberg, and D. ˇStefankoviˇ c. Fast sampling via spectral independence beyond bounded-degree graphs. ACM Transactions on Algorithms , 20(1):1–26, 2024

work page 2024

[9] [9]

Bez´ akov´ a, A

I. Bez´ akov´ a, A. Galanis, L. A. Goldberg, and D. ˇStefankoviˇ c. Inapproximability of the independent set polynomial in the complex plane. In Proceedings of the 50th annual ACM SIGACT symposium on theor y of computing , pages 1234–1240, 2018

work page 2018

[10] [10]

Bollob´ as

B. Bollob´ as. The evolution of the cube. In North-Holland Mathematics Studies . Volume 75, pages 91–97. Elsevier, 1983

work page 1983

[11] [11]

Bollob´ as, Y

B. Bollob´ as, Y. Kohayakawa, and T. /suppress Luczak. The evolution of random subgraphs of the cube. Random Structures & Algorithms , 1992

work page 1992

[12] [12]

Bollob´ as and O

B. Bollob´ as and O. Riordan. Percolation. Cambridge University Press, UK, 2006

work page 2006

[13] [13]

Campos and W

M. Campos and W. Samotij. Towards an optimal hypergraph container lemma. arXiv:2408.06617 preprint, 2024

work page arXiv 2024

[14] [14]

M. B. R. Chowdhury, S. Ganguly, and V. Winstein. Gaussia n to log-normal transition for independent sets in a percolated hypercube. arXiv:2410.07080 preprint , 2024

work page arXiv 2024

[15] [15]

Coja-Oghlan and C

A. Coja-Oghlan and C. Efthymiou. On independent sets in random graphs. Random Structures & Algo- rithms, 47(3):436–486, 2015

work page 2015

[16] [16]

Collares, J

M. Collares, J. Erde, A. Geisler, and M. Kang. Counting i ndependent sets in expanding bipartite regular graphs. arXiv:2503.22255 preprint , 2025

work page arXiv 2025

[17] [17]

Davies, M

E. Davies, M. Jenssen, and W. Perkins. A proof of the uppe r matching conjecture for large graphs. Journal of Combinatorial Theory, Series B , 151:393–416, 2021

work page 2021

[18] [18]

R. L. Dobrushin. Estimates of semi-invariants for the I sing model at low temperatures. Translations of the American Mathematical Society-Series 2 , 177:59–82, 1996

work page 1996

[19] [19]

J. Erde, M. Kang, and M. Krivelevich. Expansion in super critical random subgraphs of the hypercube and its consequences. The Annals of Probability , 51(1):127–156, 2023

work page 2023

[20] [20]

Erd˝ os and J

P. Erd˝ os and J. Spencer. Evolution of the n-cube. Computers & Mathematics with Applications , 5(1):33–39, 1979

work page 1979

[21] [21]

A. M. Frieze. On the independence number of random graph s. Discrete Mathematics, 81(2):171–175, 1990

work page 1990

[22] [22]

D. Galvin. A threshold phenomenon for random independe nt sets in the discrete hypercube. Combinatorics, probability and computing , 20(1):27–51, 2011

work page 2011

[23] [23]

D. Galvin. Independent sets in the discrete hypercube. arXiv:1901.01991 preprint , 2019

work page internal anchor Pith review Pith/arXiv arXiv 1901

[24] [24]

Galvin and J

D. Galvin and J. Kahn. On phase transition in the hard-co re model on Zd. Combinatorics, Probability and Computing, 13(2):137–164, 2004

work page 2004

[25] [25]

Galvin and P

D. Galvin and P. Tetali. On weighted graph homomorphism s. DIMACS Series in Discrete Mathematics and Theoretical Computer Science , 63:97–104, 2004

work page 2004

[26] [26]

Galvin and P

D. Galvin and P. Tetali. Slow mixing of Glauber dynamics for the hard-core model on regular bipartite graphs. Random Structures & Algorithms , 28(4):427–443, 2006

work page 2006

[27] [27]

D. J. Galvin. Bounding the partition function of spin-s ystems. The Electronic Journal of Combinatorics :R72– R72, 2006

work page 2006

[28] [28]

G. R. Grimmett. Percolation. Springer, Berlin, 1999

work page 1999

[29] [29]

Hulshof and A

T. Hulshof and A. Nachmias. Slightly subcritical hyper cube percolation. Random Structures & Algorithms , 56(2):557–593, 2020

work page 2020

[30] [30]

M. Jenssen. Personal communication, 2025

work page 2025

[31] [31]

Jenssen and P

M. Jenssen and P. Keevash. Homomorphisms from the torus . Advances in Mathematics , 430:109212, 2023

work page 2023

[32] [32]

Jenssen, A

M. Jenssen, A. Malekshahian, and J. Park. A reﬁned graph container lemma and applications to the hard-core model on bipartite expanders. arXiv:2411.03393 preprint, 2024

work page arXiv 2024

[33] [33]

Jenssen, A

M. Jenssen, A. Malekshahian, and J. Park. On Dedekind’s problem, a sparse version of Sperner’s theorem, and antichains of a given size in the Boolean lattice. arXiv:2411.03400 preprint, 2024

work page arXiv 2024

[34] [34]

Jenssen and W

M. Jenssen and W. Perkins. Independent sets in the hyper cube revisited. Journal of the London Mathe- matical Society, 102(2):645–669, 2020

work page 2020

[35] [35]

Jenssen, W

M. Jenssen, W. Perkins, and A. Potukuchi. Approximatel y counting independent sets in bipartite graphs via graph containers. Random Structures & Algorithms , 63(1):215–241, 2023

work page 2023

[36] [36]

Jenssen, W

M. Jenssen, W. Perkins, and A. Potukuchi. Independent s ets of a given size and structure in the hypercube. Combinatorics, Probability and Computing , 31(4):702–720, 2022

work page 2022

[37] [37]

Jenssen, W

M. Jenssen, W. Perkins, and A. Potukuchi. On the evoluti on of structure in triangle-free graphs. arXiv:2312.09202 preprint, 2023. 36

work page arXiv 2023

[38] [38]

Jenssen, W

M. Jenssen, W. Perkins, A. Potukuchi, and M. Simkin. Sam pling and counting triangle-free graphs near the critical density. Foundations of Computer Science , 2024

work page 2024

[39] [39]

J. Kahn. An entropy approach to the hard-core model on bi partite graphs. Combinatorics, Probability and Computing, 10(3):219–237, 2001

work page 2001

[40] [40]

Kahn and J

J. Kahn and J. Park. The number of maximal independent se ts in the Hamming cube. Combinatorica, 42(6):853–880, 2022

work page 2022

[41] [41]

G. Katona. A theorem of ﬁnite sets . In Classic Papers in Combinatorics . Birkh¨ auser Boston, 2009, pages 381– 401

work page 2009

[42] [42]

Korshunov and A

A. Korshunov and A. Sapozhenko. The number of binary cod es with distance 2. In Russian. Problemy Kibernet, 40:111–130, 1983

work page 1983

[43] [43]

Koteck´ y and D

R. Koteck´ y and D. Preiss. Cluster expansion for abstra ct polymer models. Communications in Mathematical Physics, 103:491–498, 1986

work page 1986

[44] [44]

Krivelevich, T

M. Krivelevich, T. M´ esz´ aros, P. Michaeli, and C. Shik helman. Greedy maximal independent sets via local limits. Random Structures & Algorithms , 64(4):986–1015, 2024

work page 2024

[45] [45]

Krivelevich, B

M. Krivelevich, B. Sudakov, V. H. Vu, and N. C. Wormald. O n the probability of independent sets in random graphs. Random Structures & Algorithms , 22(1):1–14, 2003

work page 2003

[46] [46]

Kronenberg and Y

G. Kronenberg and Y. Spinka. Independent sets in random subgraphs of the hypercube. arXiv:2201.06127 preprint, 2022

work page arXiv 2022

[47] [47]

J. B. Kruskal. The number of simplices in a complex . In Mathematical Optimization Techniques. University of California Press, 1963, pages 251–278

work page 1963

[48] [48]

L. Li, G. McKinley, and J. Park. The number of colorings o f the middle layers of the Hamming cube. Combinatorica, 2025

work page 2025

[49] [49]

Mattheus, D

S. Mattheus, D. Mubayi, J. Nie, and J. Verstra¨ ete. Oﬀ-d iagonal Ramsey numbers for slowly growing hypergraphs. Random Structures and Algorithms , 66(1):Paper No. e21284, 2025

work page 2025

[50] [50]

Mubayi and L

D. Mubayi and L. Yepremyan. Random Tur´ an theorem for hy pergraph cycles. arXiv:2304.15003 preprint , 2023

work page arXiv 2023

[51] [51]

R. Nenadov. Probabilistic hypergraph containers. Israel Journal of Mathematics , 261(2):879–897, 2023

work page 2023

[52] [52]

Nenadov and H

R. Nenadov and H. T. Pham. Short proof of the hypergraph c ontainer theorem. Combinatorics, Probability & Computing , 2025

work page 2025

[53] [53]

Nenadov and L

R. Nenadov and L. Verlinde. Containers with non-unifor m co-degree conditions, and an application to nearly orthogonal sets. arXiv:2411.07549 preprint , 2024

work page arXiv 2024

[54] [54]

Nikoletseas, C

S. Nikoletseas, C. Raptopoulos, and P. Spirakis. Large independent sets in general random intersection graphs. Theoretical Computer Science , 406(3):215–224, 2008

work page 2008

[55] [55]

J. Park. Note on the number of balanced independent sets in the Hamming cube. The Electronic Journal of Combinatorics :P2–34, 2022

work page 2022

[56] [56]

Long-range order in discrete spin systems

R. Peled and Y. Spinka. Long-range order in discrete spi n systems. arXiv:2010.03177 preprint, 2024

work page internal anchor Pith review Pith/arXiv arXiv 2010

[57] [57]

Potukuchi and L

A. Potukuchi and L. Yepremyan. Enumerating independen t sets in Abelian Cayley graphs. arXiv:2109.06152 preprint, 2021

work page arXiv 2021

[58] [58]

A. A. Sapozhenko. On the number of antichains in multile velled ranked posets. Discrete Mathematics and Applications, 1(2), 1991

work page 1991

[59] [59]

Saxton and A

D. Saxton and A. Thomason. Hypergraph containers. Inventiones mathematicae , 201(3):925–992, 2015

work page 2015

[60] [60]

Sly and N

A. Sly and N. Sun. Counting in two-spin models on d-regul ar graphs. The Annals of Probability , 42(6):2383– 2416, 2014

work page 2014

[61] [61]

van der Hofstad and A

R. van der Hofstad and A. Nachmias. Hypercube percolati on. Journal of the European Mathematical Society, 19(3):725–814, 2017

work page 2017

[62] [62]

D. Weitz. Counting independent sets up to the tree thres hold. In Proceedings of the thirty-eighth annual ACM Symposium on Theory of Computing , pages 140–149, 2006. 37 Appendix A. Weights of vertex sets via partition functions and entropy In this appendix, we detail some of the main ingredients that go into bounding weights of large polymers as well as t...

work page 2006

[63] [63]

orα ≥ C′ 0 log3/ 2d d1− C5/ 2 (if 1 ≤ C5< 2). These lower bounds on α hold because, when d is suﬃciently large, λ ≥ C0 log3/ 2d d1/ 2 implies that α = log(1 + λ) ≥ C0 log3/ 2d 2d1/ 2 , and likewise λ ≥ C0 log3/ 2d d1− C5/ 2 implies that α = log(1 + λ) ≥ C0 log3/ 2d 2d1− C5/ 2 . And as we mentioned above, the last term of the exponential also dominates the...

work page