pith. machine review for the scientific record. sign in

arxiv: 2605.05149 · v1 · submitted 2026-05-06 · 🧮 math.CO

Recognition: unknown

Degree-sequence bounds for independent sets via multivariate local occupancy

Ewan Davies , Juspreet Singh Sandhu , Jaehyeon Seo , Brian Tan
Authors on Pith no claims yet

Pith reviewed 2026-05-08 16:21 UTC · model grok-4.3

classification 🧮 math.CO
keywords hard-core modelindependent setsdegree sequencelocal occupancyspectral analysisgraph theorycombinatoricspartition function
0
0 comments X

The pith

New degree-sequence lower bounds are established for the expected size of independent sets in the hard-core model on graphs.

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

The paper develops new lower bounds expressed in terms of a graph's degree sequence for the expected size of an independent set sampled from the hard-core model. These bounds come in a multivariate form that applies to arbitrary graphs and a univariate form for graphs with bounded local maximum average degree such as triangle-free graphs. The proofs rely on spectral analysis of the local occupancy linear program rather than cluster expansions or induction. A sympathetic reader would care because these estimates apply under fugacities bounded by a constant over the maximum degree and could tighten understanding of independent set distributions in combinatorial and statistical mechanics settings.

Core claim

We present new degree-sequence lower bounds on the expected size of an independent set from the hard-core model. For arbitrary graphs, we establish a multivariate lower bound inspired by a conjecture of the first author and Kang and a recent bound on the multivariate partition function due to Lee and the third author. By applying a novel spectral analysis to the local occupancy linear program, our method successfully bypasses the convergence radius limitations of the cluster expansion and avoids induction. For graphs with bounded local maximum average degree, including triangle-free graphs, we prove a univariate bound extending prior work by a subset of the authors. In both cases our bounds,

What carries the argument

Spectral analysis of the local occupancy linear program, which produces the degree-sequence bounds while bypassing cluster expansion convergence limits and avoiding induction.

Load-bearing premise

The fugacities are upper bounded by c over the maximum degree of the graph for some absolute constant c depending on the setting.

What would settle it

Numerical computation of the exact hard-core expectation on a small graph with maximum degree Δ and fugacity at most c/Δ that falls below the new lower bound derived from the local occupancy program would falsify the claim.

read the original abstract

We present new degree-sequence lower bounds on the expected size of an independent set from the hard-core model. For arbitrary graphs, we establish a multivariate lower bound inspired by a conjecture of the first author and Kang and a recent bound on the multivariate partition function due to Lee and the third author. By applying a novel spectral analysis to the local occupancy linear program, our method successfully bypasses the convergence radius limitations of the cluster expansion and avoids induction. For graphs with bounded local maximum average degree, including triangle-free graphs, we prove a univariate bound extending prior work by a subset of the authors. In both cases our bounds require the fugacities to be upper bounded by $c/\Delta$ where $\Delta$ is the maximum degree of the graph and $c$ is an absolute constant depending on the setting.

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.

Referee Report

0 major / 3 minor

Summary. The manuscript establishes new degree-sequence lower bounds on the expected size of an independent set in the hard-core model. For arbitrary graphs it derives a multivariate lower bound from the local occupancy linear program, controlled via a novel spectral analysis that bypasses cluster-expansion radius limits and avoids induction; this is inspired by a conjecture of the first author with Kang and a recent multivariate partition-function bound of Lee and the third author. For graphs with bounded local maximum average degree (including triangle-free graphs) it proves a univariate extension of prior work by a subset of the authors. Both families of bounds require fugacities bounded above by c/Δ for an absolute constant c that depends on the setting.

Significance. If the spectral analysis of the local-occupancy LP is valid, the results strengthen existing degree-sequence bounds for the hard-core model by removing the need for induction and by circumventing the usual convergence-radius restrictions of cluster expansions. The multivariate formulation and the explicit handling of degree sequences represent a technical advance that could improve approximation algorithms and extremal estimates for independent sets in sparse graphs. The manuscript appropriately credits the motivating conjecture and the recent partition-function result.

minor comments (3)
  1. [Abstract] The abstract states that the spectral analysis 'successfully bypasses the convergence radius limitations of the cluster expansion' but does not indicate where in the manuscript the comparison to the radius of the cluster expansion is made explicit (e.g., which theorem or lemma quantifies the improvement). Adding a short sentence or pointer would help readers locate the precise gain.
  2. [Introduction / Main theorems] The constant c is described as 'an absolute constant depending on the setting' in both the abstract and the statement of the main theorems; an explicit dependence (or at least a concrete upper bound in terms of the local-maximum-average-degree parameter) would make the result easier to apply.
  3. [Section 2] Notation for the local-occupancy LP (variables, objective, and constraints) is introduced without a dedicated display or numbered definition; a displayed optimization problem with all symbols defined would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, accurate summary of the results, and recommendation for minor revision. The report correctly identifies the key technical contributions: the multivariate bound via spectral analysis of the local-occupancy LP, the avoidance of cluster-expansion radius limits and induction, and the univariate extension for bounded local maximum average degree graphs. We will make the minor revisions requested.

Circularity Check

0 steps flagged

Derivation self-contained via spectral analysis of local occupancy LP; no circular reductions

full rationale

The paper derives multivariate degree-sequence lower bounds for the hard-core independent-set expectation by applying a novel spectral analysis to the local occupancy linear program, explicitly bypassing cluster-expansion radius limits and avoiding induction. The fugacity restriction λ_v ≤ c/Δ is stated as an assumption. While the work is inspired by a conjecture of the first author and a prior multivariate partition-function bound involving the third author, these serve as motivation rather than load-bearing premises; the central passage from LP to degree-sequence bound rests on the independent spectral argument. No self-definitional steps, fitted inputs renamed as predictions, or ansatzes smuggled via self-citation appear. Prior-work extensions for bounded local maximum average degree are presented as extensions, not reductions to the current inputs. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review provides no explicit details on free parameters, axioms, or invented entities; standard mathematical assumptions in graph theory and probability are presumed but unlisted.

pith-pipeline@v0.9.0 · 5437 in / 1048 out tokens · 47266 ms · 2026-05-08T16:21:23.662066+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 30 canonical work pages

  1. [1]

    N. Alon. Independence numbers of locally sparse graphs and a Ramsey type problem.Random Structures & Algorithms, 9(3):271–278, 1996.doi:10.1002/(SICI)1098-2418(199610)9:3<271::AID-RSA1>3.0.CO;2-U

    work page doi:10.1002/(sici)1098-2418(199610)9:3 1996

  2. [2]

    Alon and J

    N. Alon and J. H. Spencer.The Probabilistic Method. Wiley Publishing, 4th edition, 2016

    2016

  3. [3]

    Borbényi and P

    M. Borbényi and P. Csikvari. Matchings in regular graphs: minimizing the partition function.Transactions on Combinatorics, 10(2):73–95, 2021.doi:10.22108/toc.2020.123763.1742

    work page doi:10.22108/toc.2020.123763.1742 2021

  4. [4]

    A note on Ramsey numbers

    D. Bradač, J. Fox, R. Steiner, B. Sudakov, and S. Zhang. Coloring small locally sparse degenerate graphs and related problems, 2026, arXiv:2601.15245.doi:10.48550/arXiv.2601.15245

    work page doi:10.48550/arxiv.2601.15245 2026

  5. [5]

    P. Buys, J. van den Heuvel, and R. J. Kang. Triangle-free graphs with the fewest independent sets, 2025, arXiv:2503.10002. doi:10.48550/arXiv.2503.10002

    work page doi:10.48550/arxiv.2503.10002 2025

  6. [6]

    Y. Caro. New results on the independence number. Tech Report, Tel Aviv University, 1979

    1979

  7. [7]

    Chung.Spectral Graph Theory, volume 92 ofCBMS Regional Conference Series in Mathematics

    F. Chung.Spectral Graph Theory, volume 92 ofCBMS Regional Conference Series in Mathematics. American Mathematical Society, 1996.doi:10.1090/cbms/092

    work page doi:10.1090/cbms/092 1996

  8. [8]

    R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth. On the LambertW function.Advances in Computational Mathematics, 5(1):329–359, 1996.doi:10.1007/BF02124750

    work page doi:10.1007/bf02124750 1996

  9. [9]

    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(3):730–744, 2020.doi:10.1002/rsa.20945

    work page doi:10.1002/rsa.20945 2020

  10. [10]

    Davies, R

    E. Davies, R. de Joannis de Verclos, R. J. Kang, and F. Pirot. Occupancy fraction, fractional colouring, and triangle fraction. Journal of Graph Theory, 97(4):557–568, 2021.doi:10.1002/jgt.22671

    work page doi:10.1002/jgt.22671 2021

  11. [11]

    Davies, M

    E. Davies, M. Jenssen, and W. Perkins. A proof of the upper matching conjecture for large graphs.Journal of Combinatorial Theory, Series B, 151:393–416, 2021.doi:10.1016/j.jctb.2021.07.005

    work page doi:10.1016/j.jctb.2021.07.005 2021

  12. [12]

    Davies, M

    E. Davies, M. Jenssen, W. Perkins, and B. Roberts. On the average size of independent sets in triangle-free graphs. Proceedings of the American Mathematical Society, 146(1):111–124, 2017.doi:10.1090/proc/13728

    work page doi:10.1090/proc/13728 2017

  13. [13]

    Kang, The hard-core model in graph theory, 2025, preprint, 35 pp., arXiv:2501.03379 https://arxiv.org/abs/2501.03379

    E. Davies and R. J. Kang. The hard-core model in graph theory, 2025, arXiv:2501.03379.doi:10.48550/arXiv.2501.03379

    work page doi:10.48550/arxiv.2501.03379 2025

  14. [14]

    Davies, R

    E. Davies, R. J. Kang, F. Pirot, and J.-S. Sereni. An algorithmic framework for colouring locally sparse graphs, 2020, arXiv:2004.07151.url:http://arxiv.org/abs/2004.07151

    work page arXiv 2020

  15. [15]

    Graph structure via local occupancy,https://arxiv.org/abs/2003.14361 (preprint), 2020 (cit

    E. Davies, R. J. Kang, F. Pirot, and J.-S. Sereni. Graph structure via local occupancy, 2020, arXiv:2003.14361. doi:10.48550/arXiv.2003.14361

    work page doi:10.48550/arxiv.2003.14361 2020

  16. [16]

    Davies and O

    E. Davies and O. LeBlanc. On the occupancy fraction of the antiferromagnetic Ising model, 2024, arXiv:2412.18070. doi:10.48550/arXiv.2412.18070

    work page doi:10.48550/arxiv.2412.18070 2024

  17. [17]

    Davies and W

    E. Davies and W. Perkins. Approximately counting independent sets of a given size in bounded-degree graphs.SIAM Journal on Computing, 52(2):618–640, 2023.doi:10.1137/21M1466220

    work page doi:10.1137/21m1466220 2023

  18. [18]

    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.doi:10.48550/arXiv.2505.13396

    work page doi:10.48550/arxiv.2505.13396 2025

  19. [19]

    R. A. Horn and C. R. Johnson.Matrix Analysis. Cambridge University Press, 1 edition, 1985. doi:10.1017/CBO9780511810817

    work page doi:10.1017/cbo9780511810817 1985

  20. [20]

    M. Jenssen. The cluster expansion in combinatorics. In F. Fischer and R. Johnson, editors,Surveys in Combinatorics 2024, London Mathematical Society Lecture Note Series, pages 55–88. Cambridge University Press, Cambridge, 2024. doi:10.1017/9781009490559.004

    work page doi:10.1017/9781009490559.004 2024

  21. [21]

    Kelly and L

    T. Kelly and L. Postle. Fractional coloring with local demands and applications to degree-sequence bounds on the independence number.Journal of Combinatorial Theory, Series B, 169:298–337, 2024.doi:10.1016/j.jctb.2024.07.002

    work page doi:10.1016/j.jctb.2024.07.002 2024

  22. [22]

    Lower bounds for multivariate independence polynomials and their generalisa- tions

    J. Lee and J. Seo. Lower bounds for multivariate independence polynomials and their generalisations, 2026, arXiv:2602.02450. doi:10.48550/arXiv.2602.02450

    work page doi:10.48550/arxiv.2602.02450 2026

  23. [23]

    K. Liu, S. Mohanty, P. Raghavendra, A. Rajaraman, and D. X. Wu. Locally stationary distributions: A framework for analyzing slow-mixing Markov chains. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 203–215, 2024.doi:10.1109/FOCS61266.2024.00022

    work page doi:10.1109/focs61266.2024.00022 2024

  24. [24]

    Martinsson and R

    A. Martinsson and R. Steiner. Random independent sets in triangle-free graphs.Forum of Mathematics, Sigma, 13:e156, 2025.doi:10.1017/fms.2025.10112

    work page doi:10.1017/fms.2025.10112 2025

  25. [25]

    Molloy and B

    M. Molloy and B. Reed.Graph Colouring and the Probabilistic Method. Algorithms and Combinatorics. Springer-Verlag, Berlin Heidelberg, 2002.doi:10.1007/978-3-642-04016-0

    work page doi:10.1007/978-3-642-04016-0 2002

  26. [26]

    Perarnau and W

    G. Perarnau and W. Perkins. Counting independent sets in cubic graphs of given girth.Journal of Combinatorial Theory, Series B, 133:211–242, 2018.doi:10.1016/j.jctb.2018.04.009

    work page doi:10.1016/j.jctb.2018.04.009 2018

  27. [27]

    A. Sah, M. Sawhney, D. Stoner, and Y. Zhao. The number of independent sets in an irregular graph.Journal of Combinatorial Theory, Series B, 138:172–195, 2019.doi:10.1016/j.jctb.2019.01.007

    work page doi:10.1016/j.jctb.2019.01.007 2019

  28. [28]

    Schrijver.Combinatorial optimization: polyhedra and efficiency

    A. Schrijver.Combinatorial optimization: polyhedra and efficiency. Number 24 in Algorithms and combinatorics. Springer, Berlin ; New York, 2003

    2003

  29. [29]

    A. D. Scott and A. D. Sokal. The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma.Journal of Statistical Physics, 118(5-6):1151–1261, 2005, arXiv:cond-mat/0309352.doi:10.1007/s10955-004-2055-4

    work page doi:10.1007/s10955-004-2055-4 2005

  30. [30]

    J. Seo. A lower bound on occupancy fractions, 2026.url: https://jaehyeonseo.com/assets/files/ a-lower-bound-on-occupancy-fractions.pdf. 14 E. DA VIES, JS. SANDHU, J. SEO, AND B. TAN

    2026

  31. [31]

    J. B. Shearer. A note on the independence number of triangle-free graphs.Discrete Mathematics, 46(1):83–87, 1983. doi:10.1016/0012-365X(83)90273-X

    work page doi:10.1016/0012-365x(83)90273-x 1983

  32. [32]

    J. B. Shearer. On a problem of spencer.Combinatorica, 5(3):241–245, 1985.doi:10.1007/BF02579368

    work page doi:10.1007/bf02579368 1985

  33. [33]

    J. B. Shearer. A note on the independence number of triangle-free graphs, II.Journal of Combinatorial Theory, Series B, 53(2):300–307, 1991.doi:10.1016/0095-8956(91)90080-4

    work page doi:10.1016/0095-8956(91)90080-4 1991

  34. [34]

    J. B. Shearer. On the independence number of sparse graphs.Random Structures & Algorithms, 7(3):269–271, 1995. doi:10.1002/rsa.3240070305

    work page doi:10.1002/rsa.3240070305 1995

  35. [35]

    V. Wei. A lower bound on the stability number of a simple graph. Technical Memorandum, Bell Laboratories, Bell Laboratories Technical Memorandum Murray Hill, NJ, USA, 1981. Department of Computer Science, Colorado State University, Fort Collins CO, USA Email address:research@ewandavies.org Department of Computer Science, Colorado State University, Fort Co...

    1981