Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

The hard-core model in graph theory

T0 review · 4 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For triangle-free graphs, a single local inequality on the hard-core model reproduces the best-known asymptotic bounds for independent sets, fractional colourings, and list colourings.

desk verdict A reliable and readable survey of the local occupancy method; the only real fault is an unproved negative-correlation claim in Theorem 5.4 plus a likely typo, both fixable. read the letter →

arxiv 2501.03379 v2 pith:6CNVJLZR submitted 2025-01-06 math.CO cs.DMmath.PR

Ewan Davies , Ross J. Kang This is my paper · ORCID
classification math.COcs.DMmath.PR MSC 05C1505C6905D4005C80
keywords hard-coremodellocaloccupancyindependentsetstriangle-freegraphslistcolouringfractionalchromaticnumberRamseynumbersspherepacking
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Every graph has independent sets, and the hard-core model is a weighted random way to pick one: each independent set $I$ appears with probability proportional to $\lambda^{|I|}$. This chapter argues that one local check on that random set — a balancing inequality between the chance a vertex is occupied and the expected number of occupied neighbours — is enough to control global structure. The check, called local occupancy, is verified only inside each neighbourhood, yet it produces three global conclusions: a lower bound on the expected size of a random independent set, an upper bound on the fractional chromatic number, and, under extra technical conditions, an upper bound on the list chromatic number. In triangle-free graphs the check becomes a one-variable optimisation through the Lambert $W$ function, and it reproduces the best-known asymptotic bounds: independent sets of size at least $(1-o(1))\,n\log\Delta/\Delta$ and colourings with at most $(1+o(1))\,\Delta/\log\Delta$ colours. The chapter's thesis is that this one inequality organises a large body of independence, colouring, and even sphere-packing results.

What carries the argument

The load-bearing object is the local $(\beta,\gamma)$-occupancy condition: for the hard-core distribution at fugacity $\lambda$, every vertex $u$ and every induced subgraph $F$ of $G[N(u)]$ must satisfy $\beta\,\frac{\lambda}{1+\lambda}\frac{1}{Z_F(\lambda)}+\gamma\,\frac{\lambda Z'_F(\lambda)}{Z_F(\lambda)}\ge 1$, with $Z_F(\lambda)$ the independence polynomial of $F$. It quantifies a balance between the probability that $u$ is occupied and the expected number of occupied neighbours, and it is exactly what the spatial Markov property of the hard-core model lets one verify locally. The colouring applications add a second mechanism: list colourings of $G$ are saturating independent sets in a cover graph, and local occupancy of the original graph controls the leftover lists and colour degrees in that cover, so the local lemma finishes the job.

What would settle it

Compute the hard-core distribution on a cover of a small non-triangle-free graph, for example a cover of $K_4$ with three or four colours per vertex, and check whether the indicators of two colours surviving at a fixed vertex are negatively correlated as Theorem 5.4 requires; a pair whose joint survival probability exceeds the product of the individual probabilities would falsify the theorem's general statement.

Watch

Extended reading notes

Core claim

The central claim is that the hard-core model satisfies local $(\beta,\gamma)$-occupancy if, for every vertex $u$ and every induced subgraph $F$ of its neighbourhood, $\beta\,\frac{\lambda}{1+\lambda}\frac{1}{Z_F(\lambda)}+\gamma\,\frac{\lambda Z'_F(\lambda)}{Z_F(\lambda)}\ge 1$, where $Z_F(\lambda)$ is the independence polynomial of $F$. From that single inequality the framework derives, in order of strength: an occupancy-fraction bound $\mathbb{E}|X|/|V|\ge 1/(\beta+\gamma\Delta)$; a fractional-colouring bound $\chi_f(G)\le \beta+\gamma\Delta$; and, after a local-lemma argument in a cover graph, a list-colouring bound $\chi_\ell(G)\lesssim \beta+\gamma\Delta$. In triangle-free graphs the neighbourhood subgraphs are edgeless, so $Z_F(\lambda)=(1+\lambda)^{|V(F)|}$, and minimising $\beta+\gamma d$ over $\lambda$ and $\gamma$ gives $\beta+\gamma d\sim d/\log d$ as $d\to\infty$. The chapter therefore claims that the matching asymptotic statements $\alpha(G)\ge (1-o(1))n\log\Delta/\Delta$, $\chi_f(G)\le (1+o(1))\Delta/\log\Delta$, and $\chi_\ell(G)\le (1+o(1))\Delta/\log\Delta$ all follow from this one local calculation, with smooth generalisations to locally sparse graphs, to graphs with few triangles per vertex, and to $C_k$-free graphs.

Load-bearing premise

The list-colouring conclusion rests on the assertion in Theorem 5.4 that residual list indicators in a cover are negatively correlated in every graph; the proof is carried out only for the triangle-free case and the general case is deferred to an unstated 'more involved argument', so the list-colouring theorem would not follow if that correlation failed.

Editorial extensions

If this is right

  • In every triangle-free graph of maximum degree $\Delta$, the framework guarantees an independent set of size at least $(1-o(1))\,n\log\Delta/\Delta$; through the standard bounded-degree reduction this yields the best-known asymptotic upper bound $R(3,k)\le (1+o(1))\,k^2/\log k$.
  • The same local check gives $\chi_f(G)\le (1+o(1))\,\Delta/\log\Delta$ and $\chi_\ell(G)\le (1+o(1))\,\Delta/\log\Delta$ for triangle-free $G$, recovering the current optimal colouring bounds without a separate nibbling argument.
  • For graphs with at most $t$ triangles at each vertex and $t=o(\Delta^2)$, the colouring bound becomes $(1+o(1))\Delta/\log(\Delta/\sqrt{1+t})$; for $C_k$-free graphs with $k=o(\Delta)$, it becomes $(1+o(1))\Delta/\log(\Delta/k)$.
  • In $d$-regular graphs the same framework yields sharp upper bounds on the occupancy fraction and partition function, with $K_{d,d}$ extremal for graphs and $L(K_{d,d})$ extremal for line graphs.
  • The Lambert-$W$ optimisation in the triangle-free case gives $\beta+\gamma d\sim d/\log d$, which is the quantitative engine behind all of the above and explains why $\lambda=1/\log\Delta$ is the natural fugacity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, the framework suggests an algorithmic test: whenever a graph family admits a uniform bound on $Z_F(\lambda)$ over neighbourhood subgraphs, local sampling from the hard-core model would turn the same inequality into a randomised procedure for constructing the independent sets and colourings whose existence is proved.
  • Beyond the paper, the method's blindness to global structure is itself informative: the open problem of whether bipartite graphs have list chromatic number $O(\log\Delta)$ is exactly the kind of question local occupancy cannot address, since the bipartition is invisible in any single neighbourhood.
  • Beyond the paper, Conjecture A invites a cheap computational stress test: enumerate all graphs on up to, say, eight vertices, compute $\mathbb{E}|X|$ exactly for the hard-core model, and test whether it always meets $\sum_v f_\lambda(\deg v)$; a single violation would refute the conjecture.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. This survey chapter develops the 'local occupancy' method for the hard-core model and uses it to derive global bounds on independent sets, fractional colourings, and list colourings. The core framework defines local (β,γ)-occupancy inequalities on neighbourhood subgraphs and shows that they imply lower bounds on the occupancy fraction, upper bounds on the fractional chromatic number, and, under additional concentration conditions, upper bounds on the list chromatic number. Applications are given for triangle-free graphs, graphs with bounded local triangle counts, C_k-free graphs, and regular graphs, together with a discussion of barriers and open problems. The headline claims are the asymptotic bounds for triangle-free graphs of maximum degree Δ: independence number at least (1-o(1)) n log Δ/Δ and fractional and list chromatic numbers at most (1+o(1)) Δ/log Δ, matching the best known constants.

Significance. If the listed results are fully substantiated, the chapter provides a valuable unifying survey: it connects Shearer's independence bound, Johansson's and Molloy's colouring theorems, Kahn's and Zhao's regular-graph counting results, and the authors' recent local-occupancy framework. The exposition is clear and the framework is genuinely parameter-free in the sense that the inequalities are verified locally rather than fit to data. The main weaknesses are concentrated in Section 5, where the list-colouring application rests on a concentration claim whose proof is deferred, and in a few statements whose displayed hypotheses do not match the asymptotic conclusions. These issues are local and fixable, but they currently block the paper's strongest claims.

major comments (4)
  1. [Section 5, Theorem 5.4] The proof of the Chernoff bound for |L_Y'(u)| rests on the assertion that the residual-list indicators Z'_x are negatively correlated for arbitrary covers. The proof only handles the triangle-free case, where N_H(x)\L(u) and N_H(S)\L(u) are disjoint, and defers the general case to 'a more involved argument' with no proof or reference. Since Theorem 5.5 and the list-chromatic corollaries (a)-(c) depend on this concentration estimate, the manuscript needs either a complete proof or an explicit reference (for example, to the authors' paper [32]) before this part can be considered established.
  2. [Section 5, Theorem 5.3, inequality (8.10)] The asserted conditional bound P(deg*_{H_Y'}(x) ≥ d | x ∈ L_Y'(u)) ≤ max_{F⊆G[N(u)], |V(F)|=d} 1/Z_F(λ) is not justified by the preceding argument and appears false as stated. For G=K_2 with q=1 and any λ>0, take x to be the unique element of L(u) and d=1. The event x∈L_Y'(u) forces the unique neighbour y∈L(v) to be unoccupied and to survive in the leftover cover, so the left side equals 1, while the right side equals 1/(1+λ)<1. The proof seems to support only the joint bound P(x∈L_Y'(u) and deg*_{H_Y'}(x) ≥ d) ≤ max 1/Z_F(λ), which is the form actually needed for the union bound in Theorem 5.4. The statement and proof should be corrected accordingly.
  3. [Section 4, Corollaries following Theorems 4.2, 4.5, and 4.6] The corollaries begin 'Let λ>0' but then assert bounds with leading constant 1 as Δ→∞. For fixed λ>0, Theorem 4.2 gives β+γΔ ∼ ((1+λ) log(1+λ)/λ) Δ/log Δ, so the claims α_G(λ) ≥ (1-o(1)) log Δ/Δ and χ_f(G) ≤ (1+o(1)) Δ/log Δ are false for fixed λ. The text itself notes that one must take λ→0, but the corollary statements should say explicitly that λ=λ(Δ) is allowed to depend on Δ and satisfies λ=o(1) with log(1/λ)=o(log Δ).
  4. [Section 6, proof of Theorem 6.1, inequality (8.13)] The displayed constraint (d-i-1) q_{i-1} λ ≥ i q_i is incorrect: for i=d the left-hand side is negative, which would force q_d=0 and contradict the extremal example K_{d,d}. The correct factor appears to be d-i+1, which makes the constraint an equality for K_{d,d}. Please verify and correct this display and the surrounding counting argument.
minor comments (5)
  1. [Section 5, Theorem 5.4 proof] The sufficient condition for negative correlation has a typo: the right-hand side should be P(x∉L_Y'(u)), not P(x∈L_Y'(u)). The following 'equivalent' line is consistent with the corrected version, so this is likely a simple slip, but it should be fixed.
  2. [Theorems 4.2 and 4.4] The displayed formulas for β appear to be missing a division by e log(1+λ); for example, the expression should read β = γ(1+λ)^((1+λ)/(γλ)) / (e log(1+λ)), not with the 'e log(1+λ)' factor in the numerator. If this is only a typesetting artefact, please ensure the PDF rendering is correct.
  3. [Theorem 5.5] The stated lower bound 'd ≥ 2 e log(2eΔ^3)' seems to be a typo for d ≥ (2/e) log(2eΔ^3), which is the value that makes exp(-ed/2) ≤ 1/(2eΔ^3) hold. Please correct.
  4. [Theorems 5.3 and 5.4] The phrase 'conditioned also on any realization of Y' \ L(N(u))' is ambiguous: it is unclear whether the conditioning is on the entire random set Y' outside L(N(u)) or only on its vertex set as a set. This should be clarified, since the proof of Theorem 5.2 invokes the spatial Markov property at that level of conditioning.
  5. [References] A few references are incomplete or have formatting errors, for example [32] has a duplicated comma in the arXiv field and [47] lacks volume and page details. Please check the bibliography against the volume's house style.

Circularity Check

0 steps flagged · score 2.0 of 10

No load-bearing circularity: local-occupancy bounds are derived from verified inequalities; the only flagged issue is an omitted negative-correlation proof in Theorem 5.4, which is a correctness gap, not a circular step.

full rationale

The derivation chain is self-contained at the level of the main framework. The hard-core model and local (β,γ)-occupancy are fixed definitions; Theorem 3.2 propagates the local inequality to the whole graph, Theorem 3.3 and Theorem 3.4 convert it into occupancy-fraction and fractional-chromatic bounds, and Theorem 4.2 verifies the inequality for triangle-free neighbourhoods by an explicit optimization over edgeless F, using Z_F(λ)=(1+λ)^y, with the asymptotic β+γd ~ d/log d emerging from the Lambert-W analysis rather than being imposed. No parameter is fitted to the target estimate, and no known result is merely renamed: the triangle-free and list-colouring corollaries follow from the verified inequalities plus the Lovász local lemma. Self-citations occur, for example [30, Prop. 1] for monotonicity of α_G(λ) and [32] for smooth generalizations of Molloy's theorem, but they are standard facts or attributions and are not used to force the conclusions. The genuine weakness is in Theorem 5.4: the Chernoff bound on |L_Y'(u)| requires negative correlation of the indicators Z'_x, and the proof only handles the triangle-free case, stating 'in the general case negative correlation can be established with a more involved argument' without supplying that argument or a reference; there is also a likely typo in the displayed sufficient condition, which should compare P(x∉L_Y'(u) | S∩L_Y'(u)=∅) with P(x∉L_Y'(u)) rather than P(x∈L_Y'(u)). This is an omitted proof and a correctness risk for parts (b) and (c) of the list-colouring corollary, but it is not circularity: the target bounds are not assumed in the hypotheses. Accordingly, no significant circularity; the low score reflects the minor self-citation and the unproved correlation step, neither of which makes the central claim definitionally forced.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claims rest on standard probabilistic and analytic tools rather than new postulates. The spatial Markov property is proved in the text. The Lovász local lemma, Erdős-Gallai theorem, and Lambert W asymptotics are standard inputs. The least-supported input is the negative-correlation assertion in Theorem 5.4, which is only sketched.

assumptions (5)
  • standard math Spatial Markov property of the hard-core model
    Proved in Section 3; it expresses the conditional distribution of the model on a subset as the hard-core model on the remaining uncovered subgraph, and it underpins the local occupancy inequalities.
  • standard math Lovász local lemma
    Used in Theorem 5.1 and Theorem 5.5 as a black box to show the existence of saturating independent sets in covers.
  • standard math Erdős-Gallai theorem on average degree in graphs with bounded longest path
    Used in Theorem 4.6 to bound the average degree of neighbourhood subgraphs in Ck-free graphs.
  • standard math Asymptotic expansion of the Lambert W function
    Used in Theorem 4.2 and Theorem 4.4 to derive the asymptotic forms (1+o(1))∆/log∆ from exact expressions.
  • ad hoc to paper Negative correlation of residual list indicators in general graphs
    Invoked in the proof of Theorem 5.4 to apply a Chernoff bound; the general case is asserted but not proven, with only the triangle-free case sketched.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The hard-core model in graph theory." pith.science (2026). https://pith.science/paper/6CNVJLZR

@misc{pith2026250103379,
  author       = {Pith},
  title        = {Pith review of: The hard-core model in graph theory},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6CNVJLZR}},
  note         = {Machine review of arXiv:2501.03379}
}
read the original abstract

An independent set may not contain both a vertex and one of its neighbours. This basic fact makes the uniform distribution over independent sets rather special. We consider the hard-core model, an essential generalization of the uniform distribution over independent sets. We show how its local analysis yields remarkable insights into the global structure of independent sets in the host graph, in connection with, for instance, Ramsey numbers, graph colourings, and sphere packings.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Triangle-free $d$-degenerate graphs have small fractional chromatic number

    math.CO 2025-01 accept novelty 8.0 of 10

    Every triangle-free d-degenerate graph has fractional chromatic number at most (4+o(1))d/ln d, confirming Harris's conjecture.

Reference graph

Works this paper leans on

79 extracted references · 73 canonical work pages · cited by 1 Pith paper

  1. [32]

    Davies, R

    E. Davies, R. J. Kang, F. Pirot and J.-S. Sereni, Graph structure via local occupancy, arXiv:2003.14361 [math] (2020), , arXiv: 2003.14361

    arXiv 2020

  2. [1]

    Ajtai, P

    M. Ajtai, P. Erd˝ os, J. Koml´ os and E. Szemer´ edi, On Tur´ an’s theorem for sparse graphs,Combinatorica 1 (1981), 313–317

    work page 1981

  3. [2]

    Ajtai, J

    M. Ajtai, J. Koml´ os and E. Szemer´ edi, A note on Ramsey numbers, J. Combin. Theory (A) 29 (1980), 354–360

    work page 1980

  4. [3]

    Ajtai, J

    M. Ajtai, J. Koml´ os and E. Szemer´ edi, A dense infinite Sidon sequence,Eur. J. Combin. 2 (1981), 1–11

    work page 1981

  5. [4]

    Alon, The linear arboricity of graphs, Israel J

    N. Alon, The linear arboricity of graphs, Israel J. Math. 62 (1988), 311–325

    work page 1988

  6. [5]

    Alon, Independent sets in regular graphs and sum-free subsets of finite groups, Israel J

    N. Alon, Independent sets in regular graphs and sum-free subsets of finite groups, Israel J. Math. 73 (1991), 247–256

    work page 1991

  7. [6]

    Alon, Independence numbers of locally sparse graphs and a Ramsey type problem, Random Structures Algorithms 9 (1996), 271–278

    N. Alon, Independence numbers of locally sparse graphs and a Ramsey type problem, Random Structures Algorithms 9 (1996), 271–278

    work page 1996

  8. [7]

    N. Alon, S. Cambie and R. J. Kang, Asymmetric list sizes in bipartite graphs, Ann. Comb. 25 (2021), 913–933

    work page 2021

Show all 79 references
  1. [8]

    Alon and M

    N. Alon and M. Krivelevich, The choice number of random bipartite graphs, Ann. Comb. 2 (1998), 291– 297

    1998

  2. [9]

    Alon and J

    N. Alon and J. H. Spencer, The Probabilistic Method, 4th edn., Wiley Series in Discrete Mathematics and Optimization, Wiley, 2016

    2016

  3. [10]

    van den Berg and J

    J. van den Berg and J. E. Steif, Percolation and the hard-core lattice gas model, Stochastic Process. Appl. 49 (1994), 179–197

    1994

  4. [11]

    Bernshteyn, The Johansson-Molloy theorem for DP-coloring, Random Structures Algorithms 54 (2019), 653–664

    A. Bernshteyn, The Johansson-Molloy theorem for DP-coloring, Random Structures Algorithms 54 (2019), 653–664

    2019

  5. [12]

    Bhatnagar, A

    N. Bhatnagar, A. Sly and P. Tetali, Decay of correlations for the hardcore model on the d-regular random graph, Electron. J. Probab. 21 (2016), 1–42

    2016

  6. [13]

    Bohman, The triangle-free process, Adv

    T. Bohman, The triangle-free process, Adv. Math. 221 (2009), 1653–1677

    2009

  7. [14]

    Bohman and R

    T. Bohman and R. Holzman, On a list coloring conjecture of Reed, J. Graph Theory 41 (2002), 106–109

    2002

  8. [15]

    Bohman and P

    T. Bohman and P. Keevash, Dynamic concentration of the triangle-free process, Random Structures Al- gorithms 58 (2021), 221–293

    2021

  9. [16]

    Bonamy, T

    M. Bonamy, T. Kelly, P. Nelson and L. Postle, Bounding χ by a fraction of ∆ for graphs without large cliques, J. Combin Theory (B) 157 (2022), 263–282

    2022

  10. [17]

    Bradshaw, Graph Colorings with Local Restrictions , Ph.D

    P. Bradshaw, Graph Colorings with Local Restrictions , Ph.D. thesis, Simon Fraser University, 2022

    2022

  11. [18]

    R. L. Brooks, On colouring the nodes of a network, Math. Proc. Cambridge Philos. Soc. 37 (1941), 194–197

    1941

  12. [19]

    P. Buys, J. v. d. Heuvel and R. J. Kang, Triangle-free graphs with the fewest independent sets, 2025

    2025

  13. [20]

    N. J. Calkin, On the number of sum-free sets, Bull. Lond. Math. Soc. 22 (1990), 141–144

    1990

  14. [21]

    P. J. Cameron, Portrait of a typical sum-free set, Surveys in Combinatorics 123, Cambridge Univ. Press, 1987, 13–42

    1987

  15. [22]

    P. J. Cameron and P. Erd˝ os, On the number of sets of integers with various properties, Number Theory (Banff, AB, 1988) De Gruyter, 1990, 61–79

    1988

  16. [23]

    Campos, M

    M. Campos, M. Jenssen, M. Michelen and J. Sahasrabudhe, A new lower bound for sphere packing, 2023, arXiv:2312.10026 [math]

    2023 arXiv

  17. [24]

    Campos, M

    M. Campos, M. Jenssen, M. Michelen and J. Sahasrabudhe, A new lower bound for the Ramsey numbers R(3, k), 2025

    2025

  18. [25]

    Caro, New Results on the Independence Number, Technical report, Tel-Aviv University, 1979

    Y. Caro, New Results on the Independence Number, Technical report, Tel-Aviv University, 1979. The hard-core model in graph theory 33 Davies & Kang

    1979

  19. [26]

    H. Cohn, A. Kumar, S. Miller, D. Radchenko and M. Viazovska, The sphere packing problem in dimension 24, Ann. of Math. (2) 185 (2017), 1017–1033

    2017

  20. [27]

    Coja-Oghlan and C

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

    2015

  21. [28]

    R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey and D. E. Knuth, On the Lambert W function, Adv. Comput. Math. 5 (1996), 329–359

    1996

  22. [29]

    Davies, M

    E. Davies, M. Jenssen, W. Perkins and B. Roberts, Independent sets, matchings, and occupancy fractions, J. Lond. Math. Soc. (2) 96 (2017), 47–66

    2017

  23. [30]

    Davies, M

    E. Davies, M. Jenssen, W. Perkins and B. Roberts, On the average size of independent sets in triangle-free graphs, Proc. Amer. Math. Soc. 146 (2018), 111–124

    2018

  24. [31]

    Davies, R

    E. Davies, R. J. Kang, F. Pirot and J.-S. Sereni, An algorithmic framework for colouring locally sparse graphs, arXiv:2004.07151 (2020), to appear in Theory of Computing

    2020 arXiv

  25. [33]

    Davies, J

    E. Davies, J. S. Sandhu and B. Tan, On expectations and variances in the hard-core model on bounded degree graphs, 2025, arXiv:2505.13396 [math]

    2025

  26. [34]

    Davies, R

    E. Davies, R. de Joannis de Verclos, R. J. Kang and F. Pirot, Coloring triangle-free graphs with local list sizes, Random Structures Algorithms 57 (2020), 730–744

    2020

  27. [35]

    Davies, R

    E. Davies, R. de Joannis de Verclos, R. J. Kang and F. Pirot, Occupancy fraction, fractional colouring, and triangle fraction, J. Graph Theory 97 (2021), 557–568

    2021

  28. [36]

    Erd˝ os, Graph theory and probability II, Can

    P. Erd˝ os, Graph theory and probability II, Can. J. Math. 13 (1961), 346–352

    1961

  29. [37]

    Erd˝ os and L

    P. Erd˝ os and L. Lov´ asz, Problems and results on 3-chromatic hypergraphs and some related questions, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erd˝ os on his 60th birthday), Vol. II North-Holland, Amsterdam, 1975, 609–627. Colloq. Math. Soc. J´ ano...

    1973

  30. [38]

    Erd˝ os and T

    P. Erd˝ os and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959), 337–356

    1959

  31. [39]

    Fiz Pontiveros, S

    G. Fiz Pontiveros, S. Griffiths and R. Morris, The triangle-free process and the Ramsey number r(3, k), Mem. Amer. Math. Soc. 263 (2020), 1–125

    2020

  32. [40]

    Friedli and Y

    S. Friedli and Y. Velenik, Statistical Mechanics of Lattice Systems: A Concrete Mathematical Introduction , 1st edn., Cambridge Univ. Press, 2017

    2017

  33. [41]

    Galvin and P

    D. Galvin and P. Tetali, On weighted graph homomorphisms, Graphs, Morphisms and Statistical Physics 63, Amer. Math. Soc., 2004, 97–104

    2004

  34. [42]

    Georgii, Gibbs Measures and Phase Transitions, 2nd edn., De Gruyter Studies in Mathematics, 2011

    H.-O. Georgii, Gibbs Measures and Phase Transitions, 2nd edn., De Gruyter Studies in Mathematics, 2011

    2011

  35. [43]

    Grunbaum, Research problems: A problem in graph coloring, Amer

    B. Grunbaum, Research problems: A problem in graph coloring, Amer. Math. Monthly 77 (1970), 1088– 1092

    1970

  36. [44]

    Hales, A proof of the Kepler conjecture, Ann

    T. Hales, A proof of the Kepler conjecture, Ann. of Math. (2) 162 (2005), 1065–1185

    2005

  37. [45]

    Hales, M

    T. Hales, M. Adams, G. Bauer, T. D. Dang, J. Harrison, L. T. Hoang, C. Kaliszyk, V. Magron, S. Mclaugh- lin, T. T. Nguyen, Q. T. Nguyen, T. Nipkow, S. Obua, J. Pleso, J. Rute, A. Solovyev, T. H. A. Ta, N. T. Tran, T. D. Trieu, J. Urban, K. Vu and R. Zumkeller, A formal proof o...

    2017

  38. [46]

    P. E. Haxell, A note on vertex list colouring, Combin. Probab. Comput. 10 (2001), 345–347

    2001

  39. [47]

    Hurley, R

    E. Hurley, R. De Joannis De Verclos and R. J. Kang, An improved procedure for colouring graphs of bounded local density, Adv. Comb. (2022),

    2022

  40. [48]

    T. R. Jensen and B. Toft, Graph Coloring Problems , Wiley, 1994

    1994

  41. [49]

    Jenssen, F

    M. Jenssen, F. Joos and W. Perkins, On the hard sphere model and sphere packings in high dimensions, Forum Math. Sigma 7 (2019), e1

    2019

  42. [50]

    Johansson, Asymptotic Choice Number for Triangle-Free Graphs, Technical report, DIMACS, 1996

    A. Johansson, Asymptotic Choice Number for Triangle-Free Graphs, Technical report, DIMACS, 1996

    1996

  43. [51]

    Kahn, An entropy approach to the hard-core model on bipartite graphs, Combin

    J. Kahn, An entropy approach to the hard-core model on bipartite graphs, Combin. Probab. Comput. 10 (2001), 219–237

    2001

  44. [52]

    Kahn, Entropy, independent sets and antichains: A new approach to Dedekind’s problem, Proc

    J. Kahn, Entropy, independent sets and antichains: A new approach to Dedekind’s problem, Proc. Amer. Math. Soc. 130 (2002), 371–378

    2002

  45. [53]

    R. J. Kang and C. McDiarmid, Colouring random graphs, Topics in Chromatic Graph Theory 156, Cam- bridge Univ. Press, 2015, 199–229. The hard-core model in graph theory 34 Davies & Kang

    2015

  46. [54]

    R. M. Karp, The Probabilistic Analysis of Some Combinational Search Algorithms, Technical report, EECS Department, University of California, Berkeley, 1976

    1976

  47. [55]

    Kepler, Strena Seu De Niue Sexangula , Gottfried Tampach, 1611, google-Books-ID: L3H73VJ P1EC

    J. Kepler, Strena Seu De Niue Sexangula , Gottfried Tampach, 1611, google-Books-ID: L3H73VJ P1EC

  48. [56]

    J. H. Kim, On Brooks’ theorem for sparse graphs, Combin. Probab. Comput. 4 (1995), 97–132

    1995

  49. [57]

    J. H. Kim, The Ramsey number R(3, t) has order of magnitude t2/ log t, Random Structures Algorithms 7 (1995), 173–207

    1995

  50. [58]

    Klartag, Lattice packing of spheres in high dimensions using a stochastically evolving ellipsoid, 2025, arXiv:2504.05042 [math]

    B. Klartag, Lattice packing of spheres in high dimensions using a stochastically evolving ellipsoid, 2025, arXiv:2504.05042 [math]

    2025

  51. [59]

    Krivelevich, S

    M. Krivelevich, S. Litsyn and A. Vardy, A lower bound on the density of sphere packings via graph theory, Int. Math. Res. Not. 2004 (2004), 2271–2279

    2004

  52. [60]

    Lubetzky and Y

    E. Lubetzky and Y. Zhao, On replica symmetry of large deviations in random graphs, Random Structures Algorithms 47 (2015), 109–146

    2015

  53. [61]

    Molloy, The list chromatic number of graphs with small clique number, J

    M. Molloy, The list chromatic number of graphs with small clique number, J. Combin. Theory (B) 134 (2019), 264–284

    2019

  54. [62]

    Molloy and B

    M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method , Algorithms and Combinatorics, Springer-Verlag, 2002

    2002

  55. [63]

    R. A. Moser, A constructive proof of the Lov´ asz local lemma, Proc. 41st ACM Symp. on Theory of Computing, STOC ’09, ACM, 2009, 343–350

    2009

  56. [64]

    F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. (2) 30 (1930), 264–286

    1930

  57. [65]

    Reed, ω, ∆, and χ, J

    B. Reed, ω, ∆, and χ, J. Graph Theory 27 (1998), 177–212

    1998

  58. [66]

    Reed and B

    B. Reed and B. Sudakov, Asymptotically the list colouring constants are 1, J. Combin. Theory (B) 86 (2002), 27–37

    2002

  59. [67]

    A. Sah, M. Sawhney, D. Stoner and Y. Zhao, The number of independent sets in an irregular graph, J. Combin Theory (B) 138 (2019), 172–195

    2019

  60. [68]

    A. Sah, M. Sawhney, D. Stoner and Y. Zhao, A reverse Sidorenko inequality, Invent. Math. 221 (2020),

    2020

  61. [69]

    C. E. Shannon, A mathematical theory of communication, Bell Syst. Tech. J. 27 (1948), 379–423

    1948

  62. [70]

    J. B. Shearer, A note on the independence number of triangle-free graphs, Discrete Math. 46 (1983), 83–87

    1983

  63. [71]

    J. B. Shearer, On a problem of Spencer, Combinatorica 5 (1985), 241–245

    1985

  64. [72]

    J. B. Shearer, On the independence number of sparse graphs, Random Structures Algorithms 7 (1995), 269–271

    1995

  65. [73]

    J. B. Shearer, On the average size of independent sets in triangle-free graphs, 1998, presentation at Ninth SIAM Conference on Discrete Mathematics

    1998

  66. [74]

    Spencer, Asymptotic lower bounds for Ramsey functions, Discrete Math

    J. Spencer, Asymptotic lower bounds for Ramsey functions, Discrete Math. 20 (1977), 69–76

    1977

  67. [75]

    Viazovska, The sphere packing problem in dimension 8, Ann

    M. Viazovska, The sphere packing problem in dimension 8, Ann. of Math. (2) 185 (2017), 991–1015

    2017

  68. [76]

    V. G. Vizing, Some unsolved problems in graph theory, Russian Math. Surveys 23 (1968), 125

    1968

  69. [77]

    V. K. Wei, A Lower Bound on the Stability Number of a Simple Graph, Technical report, Bell Laboratories, 1981

    1981

  70. [78]

    Zhao, The number of independent sets in a regular graph, Combin

    Y. Zhao, The number of independent sets in a regular graph, Combin. Probab. Comput. 19 (2010), 315–320

    2010

  71. [79]

    Zhao, Extremal regular graphs: Independent sets and graph homomorphisms, Amer

    Y. Zhao, Extremal regular graphs: Independent sets and graph homomorphisms, Amer. Math. Monthly 124 (2017), 827. The hard-core model in graph theory 35 Davies & Kang

    2017

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.