{"id":"599f17ed-068e-428e-b5e9-52705c6fe7e4","arxiv_id":"2501.03379","paper_version":2,"verdict":"UNVERDICTED","confidence":"HIGH","novelty_score":1.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A survey of the hard-core model and the local occupancy method, showing how local analysis of independent sets yields global bounds in graph theory.","lead":"This paper is a survey chapter explaining how the hard-core model, a probability distribution over independent sets of a graph, can be used to prove bounds on independence numbers, colourings, and Ramsey numbers. It organizes the 'local occupancy' method and its applications into a single framework for researchers in graph theory and combinatorics.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"List-colouring corollaries depend on an unproved negative-correlation claim in Theorem 5.4; the proof only handles triangle-free neighbourhoods and defers the general case, with a likely typo in the displayed sufficient condition.","rationale":"The chapter is a survey and its main deliverable is a coherent account of the local occupancy method; it does not claim a new theorem. The triangle-free independence and fractional-chromatic bounds are proved in Section 4 and do not depend on the contested step. The list-chromatic corollary, however, is the sharpest part of the strongest claim and passes through Theorem 5.5, whose proof invokes Theorem 5.4. Theorem 5.4 is the only place in the chain where the text explicitly defers a nontrivial assertion ('a more involved argument') instead of proving it or citing a result. The reader's weakest assumption identified exactly this point; I agree it is the most load-bearing condition. I do not escalate the verdict: because the chapter reports established results (Molloy; Davies–Kang–Pirot–Sereni) and the deferred claim is plausibly available in those sources, this is a gap in exposition rather than evidence of a false central claim. The proposed exhaustive test would immediately falsify the theorem if the negative-correlation assertion is wrong; absent a counterexample, the appropriate remedy is a citation or a full proof. No change to the reader's UNVERDICTED verdict is needed.","tokens_in":30520,"tokens_out":26300,"duration_ms":246332,"concrete_test":"Exhaustively enumerate all covers with q = 2 and base neighbourhood G[N(u)] on up to 4 vertices; for the hard-core model on H' = H − L(u), test the negative-correlation inequality P(∩_{y∈S}{Y' ∩ N_H(y) ≠ ∅} | Y' ∩ N_H(x) = ∅) ≥ P(∩_{y∈S}{Y' ∩ N_H(y) ≠ ∅}) for every x and S. A single violation disproves the claim as stated. If all small instances pass, consult the proof of the corresponding lemma in [32] or [34]; if the \"more involved argument\" is absent or has extra hypotheses, Theorem 5.4 should be restated with a citation or proved in full.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongest claim includes the list-chromatic-number bounds, which are obtained through Theorem 5.5. Theorem 5.5 uses the Chernoff bound in Theorem 5.4, and that bound is justified only if the residual-list indicators Z'_x = 1 - 1[x ∈ L_Y'(u)] are negatively correlated for the hard-core model on an arbitrary cover H'. The proof of Theorem 5.4 explicitly says that in the triangle-free case the sets N_H(x)\\L(u) and N_H(S)\\L(u) are disjoint, \"and in the general case negative correlation can be established with a more involved argument.\" No proof or reference is supplied for that general case. If the negative-correlation assertion fails for some cover, the bound on P(|L_Y'(u)| ≤ (1+λ)/(2βλ)(q−γΔ)) in Theorem 5.4 collapses, and with it the application of the local lemma in Theorem 5.5 and the corollary χ_ℓ(G) ≤ (1+o(1))Δ/log Δ for triangle-free G. The proof as printed also contains a likely typo: the sufficient condition should read P(x ∉ L_Y'(u) | S ∩ L_Y'(u) = ∅) ≤ P(x ∉ L_Y'(u)), not P(x ∈ L_Y'(u)); the subsequent \"equivalent\" line is consistent with the corrected version, but the slip adds uncertainty about the intended hypothesis.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":30810,"tokens_out":31004,"duration_ms":271577,"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":[{"comment":"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.","section":"Section 5, Theorem 5.4"},{"comment":"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.","section":"Section 5, Theorem 5.3, inequality (8.10)"},{"comment":"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 Δ).","section":"Section 4, Corollaries following Theorems 4.2, 4.5, and 4.6"},{"comment":"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.","section":"Section 6, proof of Theorem 6.1, inequality (8.13)"}],"minor_comments":[{"comment":"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.","section":"Section 5, Theorem 5.4 proof"},{"comment":"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.","section":"Theorems 4.2 and 4.4"},{"comment":"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.","section":"Theorem 5.5"},{"comment":"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.","section":"Theorems 5.3 and 5.4"},{"comment":"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.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The paper is a survey chapter, and several of the results are drawn from the authors' own prior papers. That is appropriate for this venue, but it also means that when a proof is deferred to 'a more involved argument', the reader is entitled to a precise reference. The Theorem 5.4 negative-correlation gap and the false statement of (8.10) are the main obstacles; both appear fixable within the scope of the chapter, so I do not recommend rejection. I would ask the editor to have the authors verify the Section 5 proof chain carefully, as the list-colouring corollaries are the strongest advertised results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a survey chapter, and judged as one it is solid. It gives a clear, well-organized account of the local occupancy framework: the toy example, the spatial Markov property, the three local-occupancy conditions, and the route from local inequalities to independence-number, fractional-colouring, and list-colouring bounds. The exposition is original even though the theorems are not. Theorem 3.1 through Theorem 6.2 come from earlier papers, many by the authors; the only candidate for a new result is Conjecture A. For a survey of one's own method, heavy self-citation is appropriate, and the chapter is candid about barriers and open problems, including the algorithmic barrier and the limits of local occupancy in bipartite list colouring. The included proofs are generally reliable, and the discussion of sharpness and the notes-added update are well done.\n\nThe real soft spot is Theorem 5.4, and the stress-test concern lands. The proof of the Chernoff bound depends on negative correlation of the residual-list indicators Z'_x = 1 - 1[x in L'_Y(u)] in an arbitrary cover. The text says the triangle-free case works because the relevant neighbourhood sets are disjoint, and 'in the general case negative correlation can be established with a more involved argument' – but no proof or reference is supplied. Since parts (b) and (c) of the list-colouring corollary rely on that general case, the chapter as printed does not fully support those corollaries. There is also a likely typo in the displayed sufficient condition: it should compare P(x not in L'_Y(u) | S ∩ L'_Y(u) = ∅) with P(x not in L'_Y(u)), not with P(x in L'_Y(u)). The equivalent condition printed below is consistent with the corrected version, so this is probably a slip, not a conceptual error. But the missing argument or citation for the general negative-correlation claim is a genuine gap in a self-contained survey.\n\nNone of this changes the value of the chapter. For a reader new to the area, or someone wanting a compact map of what local occupancy can and cannot do, this is a good entry point. The open problems are well chosen. I would send it to a referee for the volume; the referee should ask for a fix to Theorem 5.4, either a proof sketch or a precise citation, and for the typo to be corrected. With that, it is a useful survey worth having.","headline":"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.","tokens_in":31318,"tokens_out":4032,"would_cite":true,"duration_ms":37745,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C69","05D40","05C80"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["hard-core model","local occupancy","independent sets","triangle-free graphs","list colouring","fractional chromatic number","Ramsey numbers","sphere packing"],"falsifier":"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.","tokens_in":30329,"feed_emoji":"🎲","tokens_out":15575,"duration_ms":132477,"temperature":0.7,"pith_summary":"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.","feed_headline":"Local occupancy recovers best-known triangle-free colouring bounds","feed_subtitle":"A local check on each neighbourhood yields near-optimal independent sets, fractional colourings, and list colourings.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Shows that the hard-core model gives the triangle-free independence-number bound and introduces the occupancy-fraction viewpoint that the chapter develops.","marker":"[30]"},{"why":"Supplies the sharp constant in the triangle-free independence-number bound that local occupancy reproduces, the benchmark for the asymptotic statements.","marker":"[70]"},{"why":"The list-colouring theorem for triangle-free graphs that the chapter recovers as Corollary (a) of Section 5.","marker":"[61]"},{"why":"Provides the greedy fractional-colouring algorithm and local-lemma setup that convert local occupancy into global colouring bounds.","marker":"[62]"},{"why":"Introduces the linear-programming analysis of occupancy fraction, including the $d$-regular extremal bound and its line-graph refinement.","marker":"[29]"},{"why":"Develops the graph-structure-via-local-occupancy framework that is the chapter's central method and the source of its colouring corollaries.","marker":"[32]"},{"why":"Unifies local list sizes with local occupancy, the immediate antecedent of the colouring mechanism in Section 5.","marker":"[34]"},{"why":"Establishes the $O(\\Delta/\\log\\Delta)$ choice-number bound for triangle-free graphs that the local occupancy framework recovers and sharpens.","marker":"[50]"}],"fun_headline_variants":["Local occupancy check recovers best triangle-free colorings","Hard-core local rule yields near-optimal coloring bounds","One local inequality sets triangle-free coloring limits","Local hard-core occupancy gives optimal independent sets","Local occupancy: key to triangle-free coloring bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Local occupancy check recovers best triangle-free colorings","Hard-core local rule yields near-optimal coloring bounds","One local inequality sets triangle-free coloring limits","Local hard-core occupancy gives optimal independent sets","Local occupancy: key to triangle-free coloring bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000449,"raw_usage":{"total_tokens":2260,"prompt_tokens":937,"completion_tokens":1323,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":553,"completion_tokens_details":{"reasoning_tokens":1252}},"tokens_in":553,"tokens_out":1323,"duration_ms":11849,"temperature":1.0,"reasoning_tokens":1252,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:53:36.294214+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Davies, M","cited_arxiv_id":null,"evidence_quote":"Shows that the hard-core model gives the triangle-free independence-number bound and introduces the occupancy-fraction viewpoint that the chapter develops."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the sharp constant in the triangle-free independence-number bound that local occupancy reproduces, the benchmark for the asymptotic statements."},{"cited_title":"Molloy, The list chromatic number of graphs with small clique number, J","cited_arxiv_id":null,"evidence_quote":"The list-colouring theorem for triangle-free graphs that the chapter recovers as Corollary (a) of Section 5."},{"cited_title":"Molloy and B","cited_arxiv_id":null,"evidence_quote":"Provides the greedy fractional-colouring algorithm and local-lemma setup that convert local occupancy into global colouring bounds."},{"cited_title":"Davies, M","cited_arxiv_id":null,"evidence_quote":"Introduces the linear-programming analysis of occupancy fraction, including the $d$-regular extremal bound and its line-graph refinement."},{"cited_title":"Davies, R","cited_arxiv_id":null,"evidence_quote":"Unifies local list sizes with local occupancy, the immediate antecedent of the colouring mechanism in Section 5."},{"cited_title":"Johansson, Asymptotic Choice Number for Triangle-Free Graphs, Technical report, DIMACS, 1996","cited_arxiv_id":null,"evidence_quote":"Establishes the $O(\\Delta/\\log\\Delta)$ choice-number bound for triangle-free graphs that the local occupancy framework recovers and sharpens."}],"review_version":1}