Book contents
- Frontmatter
- Contents
- Preface
- Phase Transitions in Random Planar Graphs
- Extremal Poset Theory
- Techniques for Taming Temporal Graphs
- Asymptotic Enumeration via Graph Containers and Entropy
- Graph Bootstrap Percolation – A Discovery of Slowness
- Rigidity of Graphs and Frameworks: A Matroid Theoretic Approach
- Monadic Second-Order Logic for Hypergraphs and Matroids
- Domino Tilings Beyond 2D
- References
Asymptotic Enumeration via Graph Containers and Entropy
Published online by Cambridge University Press: 06 June 2026
Book contents
- Frontmatter
- Contents
- Preface
- Phase Transitions in Random Planar Graphs
- Extremal Poset Theory
- Techniques for Taming Temporal Graphs
- Asymptotic Enumeration via Graph Containers and Entropy
- Graph Bootstrap Percolation – A Discovery of Slowness
- Rigidity of Graphs and Frameworks: A Matroid Theoretic Approach
- Monadic Second-Order Logic for Hypergraphs and Matroids
- Domino Tilings Beyond 2D
- References
Summary
The container methods are powerful tools to bound the number of independent sets of graphs and hypergraphs, and they have been extremely inuential in the area of extremal and probabilistic combinatorics. We will focus on more specialized graph container methods due to Sapozhenko (1987) that deal with sets in expander graphs. Entropy, first introduced by Shannon (1948) in the area of information theory, is a measure of the expected amount of information contained in a random variable. Entropy has seen lots of fascinating applications in a wide range of enumeration problems. In this survey article, we will discuss recent developments that exploit a combination of the two methods on enumerating graph homomorphisms.
Information
- Type
- Chapter
- Information
- Surveys in Combinatorics 2026 , pp. 111 - 140Publisher: Cambridge University PressPrint publication year: 2026
References
Alon, N. and Chung, F. R. K., Explicit construction of linear sized tolerant networks, Discrete Mathematics 72 (1988), 15–19.10.1016/0012-365X(88)90189-6CrossRefGoogle Scholar
Balogh, J., Chen, C., and Garcia, R. I., Maximal independent sets in the middle layers of the Boolean lattice, preprint, arXiv:2505.00132, 2025.Google Scholar
Balogh, J., Garcia, R. I., and Li, L., Independent sets in the middle two layers of Boolean lattice, Journal of Combinatorial Theory, Series A 178 (2021), 105341.CrossRefGoogle Scholar
Balogh, J., Garcia, R. I., Li, L., and Zs, A.. Wagner, Intersecting families of sets are typically trivial, Journal of Combinatorial Theory, Series B 164 (2024), 44–67.10.1016/j.jctb.2023.09.002CrossRefGoogle Scholar
Balogh, J. and Krueger, R. A., A sharp threshold for a random version of Sperner’s theorem, Random Structures & Algorithms 62(1) (2023), 3–28.CrossRefGoogle Scholar
Balogh, J., Morris, R., and Samotij, W., Independent sets in hypergraphs, Journal of the American Mathematical Society 28(3) (2015), 669–709.CrossRefGoogle Scholar
Balogh, J., Morris, R., and Samotij, W., The method of hypergraph containers, in Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018 (2018), pp. 3059–3092.Google Scholar
Balogh, J., Mycroft, R., and Treglown, A., A random version of Sperner’s theorem, Journal of Combinatorial Theory, Series A 128 (2014), 104–110.CrossRefGoogle Scholar
Balogh, J., Treglown, A., and Zs, A.. Wagner, Applications of graph containers in the Boolean lattice, Random Structures & Algorithms 49(4) (2016), 845–872.10.1002/rsa.20666CrossRefGoogle Scholar
Benjamini, I., Häggström, O., and Mossel, E., On random graph homomorphisms into Z, Journal of Combinatorial Theory, Series B 78(1) (2000), 86–114.CrossRefGoogle Scholar
Benjamini, I., Yadin, A., and Yehudayoff, A., Random graph-homomorphisms and logarithmic degree, Electronic Journal of Probability 12 (2007), 926–950.10.1214/EJP.v12-427CrossRefGoogle Scholar
Brightwell, G. and Winkler, P., Graph homommorphisms and phase transitions, Journal of Combinatorial Theory, Series B 77 (1999), 221–262.CrossRefGoogle Scholar
Carroll, T., Cooper, J. N., and Tetali, P., Counting antichains and linear extensions in generalizations of the Boolean lattice, unpublished preprint, 2012.Google Scholar
Chung, F. R. K., Frankl, P., Graham, R., and Shearer, J. B., Some intersection theorems for ordered sets and graphs, Journal of Combinatorial Theory, Series A 48 (1986), 23–37.CrossRefGoogle Scholar
Collares, M., Erde, J., Geisler, A., and Kang, M., Counting independent sets in expanding bipartite regular graphs, preprint, arXiv:2503.22255, 2025.Google Scholar
Collares, M. and Morris, R., Maximum-size antichains in random set-systems, Random Structures & Algorithms 49 (2016), 308–321.10.1002/rsa.20647CrossRefGoogle Scholar
Das, S. and Tran, T., Removal and stability for Erdős–Ko–Rado, SIAM Journal on Discrete Mathematics 30 (2016), 1102–1114.CrossRefGoogle Scholar
Dedekind, R., Ueber zerlegungen von zahlen durch ihre grössten gemeinsamen teiler, Festschrift Hoch. Braunschweig u. ges. Werke II (1897), 103–148.Google Scholar
Duffus, D., Frankl, P., and Rödl, V., Maximal independent sets in the covering graph of the cube, Discrete Applied Mathematics 161(9) (2013), 1203–1208.10.1016/j.dam.2010.09.003CrossRefGoogle Scholar
Engbers, J. and Galvin, D., H-coloring tori, Journal of Combinatorial Theory, Series B 102(5) (2012), 1110–1133.CrossRefGoogle Scholar
Erdős, P., Ko, C., and Rado, R., Intersection theorems for systems of finite sets, The Quarterly Journal of Mathematics, Oxford Second Series 12 (1961), 313–320.CrossRefGoogle Scholar
Erdős, P. and Szekeres, G., A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470.Google Scholar
Falgas-Ravry, V., Räty, E., Tomon, I., Dedekind’s problem in the hypergrid, preprint, arXiv:2310.12946, 2023.Google Scholar
Fox, J., Pach, J., Sudakov, B., and Suk, A., Erdős–Szekeres-type theorems for monotone paths and convex bodies, Proceedings of the London Mathematical Society 105(5) (2012), 95300982.10.1112/plms/pds018CrossRefGoogle Scholar
Galvin, D., On homomorphisms from the Hamming cube to Z, Israel Journal of Mathematics 138 (2003), 189–213.10.1007/BF02783426CrossRefGoogle Scholar
Galvin, D., A threshold phenomenon for random independent sets in the discrete hypercube, Combinatorics, Probability and Computing 20(1) (2011), 27–51.CrossRefGoogle Scholar
Galvin, D., Independent sets in the discrete hypercube, preprint, arXiv: 1901.01991, 2019.Google Scholar
Galvin, D. and Tetali, P., On weighted graph homomorphisms, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 63 (2004), 97–104.10.1090/dimacs/063/07CrossRefGoogle Scholar
Galvin, D. and Tetali, P., Slow mixing of Glauber dynamics for the hard-core model on regular bipartite graphs, Random Structures & Algorithms 28(4) (2006), 427–443.10.1002/rsa.20094CrossRefGoogle Scholar
Geisler, A., Kang, M., Sarantis, M., and Wdowinski, R., Counting independent sets in percolated graphs via the Ising model, preprint, arXiv:2504.08715, 2025.Google Scholar
Hamm, A. and Kahn, J., On Erdős–Ko–Rado for random hypergraphs II, Com-binatorics, Probability and Computing 28 (2019), 61–80.10.1017/S0963548318000433CrossRefGoogle Scholar
Hujter, M. and Tuza, Z., The number of maximal independent sets in triangle-free graphs, SIAM Journal on Discrete Mathematics 6 (1993), 284–288.10.1137/0406022CrossRefGoogle Scholar
Ilinca, L. and Kahn, J., Counting maximal antichains and independent sets, Order 30 (2013), 427–435.CrossRefGoogle Scholar
I¸sık, S. and Park, J., Random Lipschitz functions on graphs with weak expansion, preprint, arXiv:2411.09640, 2024.Google Scholar
Jäkel, C., A computation of the ninth Dedekind Number, preprint, arXiv: 2304.00895, 2023.10.1016/j.jaca.2023.100006CrossRefGoogle Scholar
Jenssen, M., The cluster expansion in combinatorics, Surveys in combinatorics 493 (2024), 55–88.Google Scholar
Jenssen, M. and Keevash, P., Homomorphisms from the torus, Advances in Mathematics 430 (2023), 109212.CrossRefGoogle Scholar
Jenssen, M., Malekshahian, A., and Park, J., A refined graph container lemma and applications to the hard-core model on bipartite expanders, preprint, arXiv:2411.03393, 2024.Google Scholar
Jenssen, M., Malekshahian, A., and Park, J., On Dedekind’s problem, a sparse version of Sperner’s theorem, and antichains of a given size in the Boolean lattice, preprint, arXiv:2411.03400, 2024.Google Scholar
Jenssen, M., Park, J., and Sarantis, M., On the number of antichains in {0, 1, 2}n, in preparation.Google Scholar
Jenssen, M. and Perkins, W., Independent sets in the hypercube revisited, Journal of the London Mathematical Society 102 (2020), 645–669.CrossRefGoogle Scholar
Jenssen, M., Perkins, W., and Potukuchi, A., Approximately counting independent sets in bipartite graphs via graph containers, Random Structures & Algorithms 63(1) (2023), 215–241.CrossRefGoogle Scholar
Jenssen, M., Perkins, W., and Potukuchi, A., Independent sets of a given size and structure in the hypercube, Combinatorics, Probability and Computing 31(4) (2022), 215–241.10.1017/S0963548321000559CrossRefGoogle Scholar
Kahn, J., An entropy approach to the hard-core model on bipartite graphs, Combinatorics, Probability and Computing 10(3) (2001), 219–237.10.1017/S0963548301004631CrossRefGoogle Scholar
Kahn, J., Entropy, independent sets and antichains: a new approach to Dedekind’s problem, Proceedings of the American Mathematical Society 130 (2001), 371–378.10.1090/S0002-9939-01-06058-0CrossRefGoogle Scholar
Kahn, J., Range of cube-indexed random walk, Israel Journal of Mathematics 124 (2001), 189-201.10.1007/BF02772616CrossRefGoogle Scholar
Kahn, J. and Park, J., An isoperimetric inequality for the Hamming cube and some consequences, Proceedings of the American Mathematical Society 149 (2020), 4213–4224.10.1090/proc/15105CrossRefGoogle Scholar
Kahn, J. and Park, J., The number of 4-colorings of the Hamming cube, Israel Journal of Mathematics 236 (2020), 629–649.CrossRefGoogle Scholar
Kahn, J. and Park, J., The number of maximal independent sets in the Hamming cube, Combinatorica 42(6) (2022), 853–880.CrossRefGoogle Scholar
Kleitman, D., On Dedekind’s problem: The number of monotone Boolean functions, Proceedings of the American Mathematical Society 21 (1969), 677–682.Google Scholar
Kleitman, D. and Markowsky, G., On Dedekind’s problem: the number of isotone Boolean functions. II, Transactions of the American Mathematical Society 213 (1975), 373–390.Google Scholar
Kleitman, D. and Winston, K., On the number of graphs without 4-cycles, Discrete Mathematics 41(2) (1982), 167–172.10.1016/0012-365X(82)90204-7CrossRefGoogle Scholar
Korshunov, A. D., The number of monotone Boolean functions, Problemy Kiber-netiki 31 (1981), 5–108.Google Scholar
Korshunov, A. D. and Sapozhenko, A. A., The number of binary codes with distance 2, Problemy Kibernet 40 (1983), 111–130.Google Scholar
Kronenberg, G. and Spinka, Y., Independent sets in random subgraphs of the hypercube, preprint, arXiv:2201.06127, 2022.Google Scholar
Krueger, R. A., Li, L. and Park, J., Lipschitz functions on weak expanders, preprint, arXiv:2408.14702, 2024.Google Scholar
Li, L., McKinley, G., and Park, J., The number of colorings of the middle layers of the Hamming cube, Combinatorica 45 (2025), 1–47.CrossRefGoogle Scholar
Milans, K., Stolee, D., and West, D., Ordered Ramsey theory and track representations of graphs, Journal of Combinatorics 6 (2015), 445–456.10.4310/JOC.2015.v6.n4.a3CrossRefGoogle Scholar
Moon, J. W. and Moser, L., On cliques in graphs, Israel Journal of Mathematics 3 (1965), 23–28.10.1007/BF02760024CrossRefGoogle Scholar
Moshkovitz, G. and Shapira, A., Ramsey theory, integer partitions and a new proof of the Erdős–Szekeres theorem, Advances in Mathematics 262 (2012), 1107–1129.10.1016/j.aim.2014.06.008CrossRefGoogle Scholar
Noel, J., Scott, A., and Sudakov, B., Supersaturation in posets and applications involving the container method, Journal of Combinatorial Theory, Series A 154 (2018), 247–284.10.1016/j.jcta.2017.08.019CrossRefGoogle Scholar
Osthus, D., Maximum antichains in random subsets of a finite set, Journal of Combinatorial Theory, Series A 90 (2000), 336–346.10.1006/jcta.1999.3048CrossRefGoogle Scholar
Park, J., Note on the number of balanced independent sets in the Hamming cube, The Electronic Journal of Combinatorics 29 (2022), 2–34.10.37236/10471CrossRefGoogle Scholar
Park, J., Sarantis, M., and Tetali, P., Note on the number of antichains in generalizations of the Boolean lattice, Combinatorial Theory (to appear).Google Scholar
Peled, R., High-dimensional Lipschitz functions are typically flat, The Annals of Probability 45(3) (2017), 1351–1447.10.1214/16-AOP1089CrossRefGoogle Scholar
Peled, R., Samotij, W., and Yehudayoff, A., Grounded Lipschitz functions on trees are typically flat, Electronic Communications in Probability 18 (2013), 1–9.10.1214/ECP.v18-2796CrossRefGoogle Scholar
Peled, R., Samotij, W., and Yehudayoff, A., Lipschitz functions on expanders are typically flat, Combinatorics, Probability and Computing 22(4) (2013), 566–591.CrossRefGoogle Scholar
Peled, R. and Spinka, Y., Long-range order in discrete spin systems, preprint, arXiv:2010.03177, 2024.Google Scholar
Pippenger, N., Entropy and enumeration of Boolean functions, IEEE Transactions on Information Theory 45 (1999), 2096–2100.10.1109/18.782146CrossRefGoogle Scholar
Pohoata, C. and Zakharov, D., On the number of high-dimensional partitions, Proceedings of the London Mathematical Society 128(2) (2024), e12586.10.1112/plms.12586CrossRefGoogle Scholar
Potukuchi, A. and Yepremyan, L., Enumerating independent sets in Abelian Cayley graphs, preprint, arXiv:2109.06152, 2021.Google Scholar
Sapozhenko, A. A., On the number of antichains in multilevelled ranked posets, Discrete Mathematics and Applications 1(2) (1991), 149–169.10.1515/dma.1991.1.2.149CrossRefGoogle Scholar
Sapozhenko, A. A., On the number of connected subsets with given cardinality of the boundary in bipartite graphs, Metody Diskretnogo Analiza 45 (1987), 42–70.Google Scholar
Sapozhenko, A. A., On the number of independent sets in expanders, Discrete Mathematics 13(1) (2001), 56–62.Google Scholar
Sapozhenko, A. A., Systems of containers and enumeration problems, in Stochastic Algorithms: Foundations and Applications (ed. Lupanov, O. B., Kasim-Zade, O. M., Chaskin, A. V., and Steinhöfel, K.), Springer Berlin Heidelberg, Berlin, Heidelberg (2005), pp. 1–13.Google Scholar
Saxton, D. and Thomason, A., Hypergraph containers, Inventiones mathematicae 201(3) (2015), 925–992.10.1007/s00222-014-0562-8CrossRefGoogle Scholar
Shannon, C., A mathematical theory of communication, Bell System Technical Journal 27(3) (1948), 379–423.10.1002/j.1538-7305.1948.tb01338.xCrossRefGoogle Scholar
Sperner, E., Ein Satz ¨uber Untermengen einer endlichen Menge, Mathematische Zeitschrift 27(1) (1928), 544–548.10.1007/BF01171114CrossRefGoogle Scholar
Tsai, S. F., A simple upper bound on the number of antichains in [t]n, Order 36 (2019), 507–510.10.1007/s11083-018-9480-5CrossRefGoogle Scholar
Van Hirtum, L., De Causmaecker, P., Goemaere, J., Kenter, T., Riebler, H., Lass, M., and Plessl, C., A computation of D(9) using FPGA Supercomputing, preprint, arXiv:2304.03039, 2023.Google Scholar
Weitz, D., Counting independent sets up to the tree threshold, Symposium on the Theory of Computing (2006), 140–149.10.1145/1132516.1132538CrossRefGoogle Scholar
Wiedemann, D., A computation of the eighth Dedekind number, Order 8 (1991), 5–6.10.1007/BF00385808CrossRefGoogle Scholar
Accessibility standard: WCAG 2.2 A
Why this information is here
This section outlines the accessibility features of this content - including support for screen readers, full keyboard navigation and high-contrast display options. This may not be relevant for you.Accessibility Information
The PDF of this chapter complies with version 2.2 of the
Web Content Accessibility Guidelines
(WCAG), offering more comprehensive accessibility measures for a broad range
of users and meets the basic
(A)
level of WCAG compliance, addressing essential accessibility barriers.
Content Navigation
Table of contents navigation
Allows you to navigate directly to chapters, sections, or non‐text items through a linked table of contents, reducing the need for extensive scrolling.
Allows you to navigate directly to chapters, sections, or non‐text items through a linked table of contents, reducing the need for extensive scrolling.
Index navigation
Provides an interactive index, letting you go straight to where a term or subject appears in the text without manual searching.
Provides an interactive index, letting you go straight to where a term or subject appears in the text without manual searching.
Reading Order & Textual Equivalents
Single logical reading order
You will encounter all content (including footnotes, captions, etc.) in a clear, sequential flow, making it easier to follow with assistive tools like screen readers.
You will encounter all content (including footnotes, captions, etc.) in a clear, sequential flow, making it easier to follow with assistive tools like screen readers.
Short alternative textual descriptions
You get concise descriptions (for images, charts, or media clips), ensuring you do not miss crucial information when visual or audio elements are not accessible.
You get concise descriptions (for images, charts, or media clips), ensuring you do not miss crucial information when visual or audio elements are not accessible.