Pith. sign in

REVIEW 2 major objections 4 minor 37 references

On the independent set polynomial of graphs and claw-free graphs

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper proves that every claw-free graph of maximum degree $\Delta$ has an independence polynomial with no zeros in the disk of radius $1/(2\Delta+1)$, a degree-only bound that beats Shearer's radius and approaches the Heilmann–Lieb…

desk verdict The claw-free zero-free bound is real and new, but the paper needs a round of corrections: an off-by-one in (2.4), a false abstract claim for small Delta, and a bad special-value formula. read the letter →

arxiv 2505.22766 v2 pith:UCLW3UUF submitted 2025-05-28 math.CO math-phmath.MP

Paula M. S. Fialho , Aldo Procacci This is my paper
classification math.COmath-phmath.MP MSC 05C3105C6905C7582B20
keywords independencepolynomialclaw-freegraphszero-freeregionclusterexpansionabstractpolymergasHeilmann-LiebboundShearerradiuspartitionscheme
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

This paper makes two claims about the independence polynomial $Z_G(z)$, the generating function that counts independent sets of a graph by their size. For claw-free graphs, graphs with no induced three-leaf star, it enlarges the known zero-free disk around the origin: writing $\Delta$ for the maximum degree and $\Phi$ for the largest number of independent pairs inside any vertex's neighborhood, the polynomial has no zeros whenever $|z| \le 1/(\Delta+1+2\sqrt{\Phi})$, and a degree-only version gives the radius $1/(2\Delta+1)$. This radius is larger than the classical Shearer radius for $\Delta \ge 4$ and asymptotically matches the best known constant for line graphs. The second claim is an exact forest decomposition of $Z_G(z)$, expressing it as $(1+z)^{|V|}$ times a signed sum over forests selected by a partition scheme. A careful reader should care because zero-free disks of the independence polynomial control phase transitions in hard-core lattice gases, the Lovász local lemma, and interpolation methods for approximate counting.

What carries the argument

The load-bearing mechanism is the cluster-expansion criterion of Theorem 1.1: given nonnegative weights $\mu_v$, the multivariate independence polynomial is nonzero on the polydisc $|z_v| \le \mu_v/(\mu_v+\varphi_v(\mu))$, where $\varphi_v(\mu)$ is the independent-set sum over the neighborhood of $v$. The present contribution is to evaluate this neighborhood function in the claw-free case, where it has at most a quadratic growth, and to optimize the resulting ratio. For the forest identity, the central object is a partition scheme $m$, a rule that assigns to each tree a larger spanning connected subgraph in a consistent way; together with the Penrose identity, it turns alternating sums over connected subgraphs into sums over spanning trees, which yields the signed forest expansion of $Z_G(z)$.

What would settle it

Compute the independence polynomial of a claw-free 4-regular graph whose vertex neighborhoods achieve $\Phi=4$ and check whether all roots lie outside the disk $|z|<1/9$; a single root inside that disk would refute the degree-only bound.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the cluster-expansion criterion quoted as Theorem 1.1 becomes quantitative for claw-free graphs. Because no vertex neighborhood in a claw-free graph contains three mutually nonadjacent vertices, the independent-set sum $\varphi_v(\mu)$ over a neighborhood is bounded by a quadratic in the activity, $1+(\Delta+1)\mu+\Phi\mu^2$, and optimizing $\mu/(1+(\Delta+1)\mu+\Phi\mu^2)$ yields the zero-free disk of radius $1/(\Delta+1+2\sqrt{\Phi})$. Using Mantel's theorem to bound $\Phi \le \Delta^2/4$ gives the degree-only corollary $\lambda_1(G) \le -1/(2\Delta+1)$ for the negative root closest to the origin, a Heilmann–Lieb-type statement that now covers all claw-free graphs. The paper also proves a structural identity, $Z_G(z)=(1+z)^{|V|}\sum_{F\in\mathcal{F}_{G,m}}(-1)^{|F|}\left(\frac{z}{1+z}\right)^{|V_F|}$, valid for any partition scheme $m$, which rewrites the polynomial as a polymer-gas partition function over forests of $m$-invariant trees.

Load-bearing premise

The claw-free bounds depend entirely on an earlier cluster-expansion theorem that this paper quotes without proof, so if that theorem carries any hidden extra assumption, the new bounds would not follow.

Editorial extensions

If this is right

  • Every claw-free graph of maximum degree $\Delta$ has an independence polynomial with no zeros in the disk $|z| \le 1/(2\Delta+1)$ around the origin.
  • For $\Delta \ge 4$ this radius is strictly larger than the classical Shearer radius, so it improves the best degree-only lower bound on the distance to the closest zero.
  • As $\Delta$ grows, $1/(2\Delta+1)$ is asymptotically equal to the Heilmann–Lieb constant for line graphs, so the main bound extends the monomer-dimer zero-free regime to all claw-free graphs.
  • When the local independent-pair count $\Phi$ is small, the refined radius $1/(\Delta+1+2\sqrt{\Phi})$ beats the degree-only bound, making neighborhood structure a quantitative resource for enlarging the zero-free region.
  • At $z=-1$, the forest identity expresses the reduced Euler characteristic of the independence complex as an alternating count of spanning forests whose trees are invariant under the chosen partition scheme.

Reading between the lines

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

  • The $\Phi$-dependent bound suggests that counting local independent pairs exactly for structured claw-free subclasses, such as quasi-line graphs, should give sharper zero-free radii; this is a computable prediction that can be checked against numerical root locations.
  • The same polymer-gas rewriting that proves identity (3.2) should extend to the multivariate independence polynomial, yielding a weighted forest formula that might provide zero-free polydiscs under weaker assumptions than the cluster-expansion criterion requires.
  • Because the cluster-expansion criterion is imported from the authors' earlier work and is unproved here, the first numerical counterexample to the degree-only bound would point to a hidden hypothesis in that criterion rather than to an error in the quadratic neighborhood estimate.
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

2 major / 4 minor

Summary. The manuscript studies the independent set polynomial Z_G(z) of a finite simple graph. In Section 2 it applies the Fernández–Procacci cluster-expansion criterion to claw-free graphs. Since every independent set in the neighborhood of a vertex in such a graph has size at most two, the authors derive the zero-free radius 1/(Δ+1+2√Φ), where Δ is the maximum degree and Φ is the maximum number of independent pairs in a neighborhood, and hence the bound λ1(G) ≤ -1/(Δ+1+2√Φ). Using Mantel's theorem to bound Φ ≤ Δ²/4, they obtain the degree-only bound λ1(G) ≤ -1/(2Δ+1). Section 3 establishes a forest expansion Z_G(z) = (1+z)^{|V|} ∑_{F∈F_{G,m}} (-1)^{|F|} (z/(1+z))^{|V_F|}, together with corollaries evaluating Z_G at z=-1, -1/2 and 1.

Significance. If the stated results hold, Section 2 provides a degree-based zero-free bound for claw-free graphs that complements the real-rootedness theorem of Chudnovsky–Seymour and improves on the Shearer radius for large maximum degree; the Φ-dependent form is new and natural. Section 3 is an elegant application of Penrose identities and may be of independent interest. The proof is built on a published and parameter-free theorem (Fernández–Procacci), so the reliance on that theorem is not a hidden assumption. However, the significance is currently undercut by an incorrect displayed inequality in the proof of Theorem 2.2 and by an unqualified 'exceeds Shearer' claim in the abstract; both issues are correctable without changing the main conclusions.

major comments (2)
  1. [§2, inequality (2.4) and Theorem 2.2 proof] The displayed inequality φ_v(μ) ≤ 1+(Δ+1)μ+Φμ² is not correct for the function φ_v defined in (2.2): in a claw-free graph φ_v(μ) = 1 + d_v μ + s_v μ², and since d_v ≤ Δ and s_v ≤ Φ, the correct bound is φ_v(μ) ≤ 1 + Δμ + Φμ². The final radius in (2.5) is nonetheless correct because Corollary 2.1 has denominator μ + φ_v(μ), so μ + φ_v(μ) ≤ 1 + (Δ+1)μ + Φμ²; the proof should be rewritten as this two-step argument. The Schläfli example should also be corrected: for the 16-regular Schläfli graph φ_v(μ) = 1 + 16μ + 40μ², not 1 + 17μ + 40μ², and the later denominator 1 + 17μ + 40μ² is correct only after adding the μ from Corollary 2.1. As printed, the proof does not justify the constants in (2.5).
  2. [Abstract and Corollary 2.3] The abstract states without qualification that the bound exceeds the classical Shearer radius. This is false for small maximum degree with the stated Corollary 2.3: for Δ=3, 1/(2Δ+1)=1/7≈0.1429 while Shearer's radius is r_3=4/27≈0.1481, and for Δ=2, 1/5<1/4. The improvement is genuine for Δ≥4, and asymptotically the bound matches the Heilmann–Lieb constant, but the assertion must be qualified, for example by writing 'exceeds the Shearer radius for Δ≥4' or by comparing the Φ-dependent bound of Theorem 2.2 on a case-by-case basis.
minor comments (4)
  1. [§2, Corollary 2.3 proof] The sentence 'as the complement of a triangle-free graph is a claw-free graph' is misleading; the relevant argument is that for a claw-free graph the induced subgraph on Γ_G(u) has no independent set of size 3, so its complement is triangle-free and Mantel's theorem applies to that complement. Please rephrase.
  2. [§2, notation] The two radii denoted rΔ and r̃Δ in the discussion following Corollary 2.1 are visually almost identical; please use clearly distinct symbols.
  3. [§3, proof of Theorem 3.2] After equation (3.7), the sentence saying that the k=0 term 'corresponds to the partition of V in |V| subsets each of cardinality 1' is imprecise: in the factored polymer-sum expression the k=0 term corresponds to the empty family of polymer blocks after the factor (1+z)^{|V|} has been extracted. Please rephrase.
  4. [Throughout] There are several typos and spacing errors that should be corrected: 'modulous', 'F ern´ andez', 'i f', 'charateristic', and 'of of z'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central zero-free bounds are derived from an independent published cluster-expansion theorem applied to a graph-structural estimate, with no fitted input renamed as a prediction.

full rationale

The paper's load-bearing engine is Theorem 1.1, the Fernandez-Procacci cluster-expansion criterion, cited from the authors' own prior paper [18]. This is self-citation, but it is not circular: the theorem is a published, parameter-free statement whose stated hypotheses are finite graphs with nonnegative weights, and it does not assume or contain the claw-free zero-free-radius claims derived in Theorem 2.2. The new content is the estimate (2.4), which follows from the claw-free structural fact that independent sets in a neighborhood have size at most two, together with the definitions of Delta and Phi. This estimate is not fitted to the target zeros, and the subsequent optimization over mu is shown explicitly. The result is then tested against independent external anchors: the exact Schlafli root, the Heilmann-Lieb constant, and the Leake-Ryder bounds, so the central claim is falsifiable outside the paper's own fitted values. Section 3's alternative representation is derived by a direct algebraic cluster expansion and uses the standard Penrose identity as Lemma 3.3; the derivation is written out and the representation reduces to the definition of Z_G(z) by elementary manipulation rather than by assuming the conclusion. There is no self-definitional step, no fitted parameter renamed as a prediction, no uniqueness assertion imported from the authors' prior work, and no ansatz smuggled in through citation. The apparent off-by-one coefficient in inequality (2.4), where a Delta-regular vertex contributes d_v mu rather than (Delta+1) mu, affects the tightness of the stated constants and the claim about exceeding Shearer for small Delta, but this is a correctness or sharpness issue, not a circularity. Under the hard rule that self-citation is circular only when the load-bearing argument reduces to an unverified self-citation, no such reduction occurs here; the appropriate finding is no significant circularity.

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

No free parameters: mu is optimized in closed form at mu = 1/sqrt(Phi), and Delta and Phi are graph invariants stated in the hypotheses, not adjustable constants. The central claims rest on the five axioms listed, of which the Fernandez-Procacci criterion and the Penrose identity are the authors' own published theorems (cited, not proved here). No new entities are invented; the partition scheme of Definition 3.1 is a standard object from the Penrose/forest literature. The paper's added value is a new application of stated background theorems, with no fitted quantities.

assumptions (5)
  • domain assumption Fernandez-Procacci criterion: for any nonnegative mu, Z_G is nonzero in the polydisc |z_v| <= mu_v/(mu_v + phi_v(mu)) (Theorem 1.1)
    Self-cited theorem from the authors' prior work [18] (Comm. Math. Phys. 274, 2007), used without proof as the engine for Theorem 2.2 and Corollary 2.3. Parameter-free and published, so treated as background, but the claw-free bounds inherit exactly its hypotheses.
  • domain assumption Penrose identity: for any partition scheme m, sum_{E in C_R} (-1)^{|E|} = (-1)^{|R|-1} |T^m_R| (Lemma 3.3)
    Also from [18]; converts connected-subgraph alternating sums into tree sums in the proof of Theorem 3.2. Existence of partition schemes is asserted by reference to [32,18,22,37,34,19] rather than constructed in this paper.
  • standard math Mantel's theorem: a triangle-free graph on n vertices has at most n^2/4 edges
    Used in Corollary 2.3 to derive Phi <= Delta^2/4 from the fact that the complement of each neighborhood is triangle-free in a claw-free graph.
  • domain assumption In a claw-free graph every independent set inside a neighborhood has size at most 2
    Elementary consequence of the K_{1,3}-free definition; it reduces phi_v(mu) to a quadratic and is the basis of bound (2.4).
  • standard math Chudnovsky-Seymour: independence polynomials of claw-free graphs have only real (negative) roots [7]
    Gives lambda_1(G) its meaning as the closest root; not needed for the zero-free disk itself, which is the primary claim.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the independent set polynomial of graphs and claw-free graphs." pith.science (2026). https://pith.science/paper/UCLW3UUF

@misc{pith2026250522766,
  author       = {Pith},
  title        = {Pith review of: On the independent set polynomial of graphs and claw-free graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UCLW3UUF}},
  note         = {Machine review of arXiv:2505.22766}
}
abstract

We present two new contributions to the study of the independence polynomial $Z_G(z)$ of a finite simple graph $G = (V,E)$. First, we provide an improved lower bound for the zero-free region of $Z_G(z)$ for the important class of claw-free graphs. Our bound exceeds the classical Shearer radius and it is derived through a refined application of the Fern\'andez-Procacci criterion using properties of the local neighborhood structure in claw-free graphs. Second, we establish a novel combinatorial expression for $Z_G(z)$, inspired by the connection with the abstract polymer gas models in statistical mechanics, which offers a new structural interpretation of the polynomial and may be of independent interest. These results strengthen the connection between statistical physics, combinatorics, and graph theory, and suggest new approaches for analytic exploration.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

37 extracted references · 36 canonical work pages

  1. [1]

    Barvinok, Combinatorics and Complexity of Partition Functions , Algorithms and Com- binatorics 30, Springer (2016)

    A. Barvinok, Combinatorics and Complexity of Partition Functions , Algorithms and Com- binatorics 30, Springer (2016)

    work page 2016

  2. [2]

    Bencs, P

    F. Bencs, P. Buys, H. Peters, The Limit of the Zero Locus of the Independence Polynomial for Bounded Degree Graphs, Michigan Math. J. Advance Publication 1-26 (2024)

    work page 2024

  3. [3]

    Bencs, P

    F. Bencs, P. Csikv´ ari, P. Srivastava, J. Vondr´ ak,On complex roots of the independence polynomial, In Proc. 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA) , SIAM, 675-699 (2023)

    work page 2023

  4. [4]

    Bencs, G

    F. Bencs, G. Regts, Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs, preprint arXiv:2505.04366 (2025)

    arXiv 2025

  5. [5]

    Bissacot, R

    R. Bissacot, R. Fern´ andez, A. Procacci, B. Scoppola, An Improvement of the Lov´ asz Local Lemma via Cluster Expansion , Comb. Probab. Comput. 20 (5), 709-719 (2011)

    work page 2011

  6. [6]

    A. E. Brouwer, H. Van Maldeghem, Strongly Regular Graphs, Cambridge University Press (2022)

    work page 2022

  7. [7]

    Chudnovsky, P

    M. Chudnovsky, P. D. Seymour, The roots of the independence polynomial of a claw-free graph, J. Combin. Theory Ser. B 97 (3), 350-357 (2007)

    work page 2007

  8. [8]

    Chudnovsky, P

    M. Chudnovsky, P. D. Seymour, The structure of claw-free graphs , In B. S. Webb (ed.), Surveys in Combinatorics 2005 , London Mathematical Society Lecture Note Series 327, Cambridge University Press, 153-171 (2005). 11

    work page 2005

Show all 37 references
  1. [9]

    Chudnovsky, P

    M. Chudnovsky, P. D. Seymour, Claw-free graphs. I. Orientable prismatic graphs , J. Com- bin. Theory Ser. B 97, 1373-1410 (2007)

    2007

  2. [10]

    Chudnovsky, P

    M. Chudnovsky, P. D. Seymour, Claw-free graphs. II. Non-orientable prismatic graphs , J. Combin. Theory Ser. B 98, 249-290 (2008)

    2008

  3. [11]

    Chudnovsky, P

    M. Chudnovsky, P. D. Seymour, Claw-free graphs. III. Circular interval graphs , J. Combin. Theory Ser. B 98, 812-834 (2008)

    2008

  4. [12]

    Chudnovsky, P

    M. Chudnovsky, P. D. Seymour, Claw-free graphs. IV. Decomposition theorem, J. Combin. Theory Ser. B 98, 839-938 (2008)

    2008

  5. [13]

    Chudnovsky, P

    M. Chudnovsky, P. D. Seymour, Claw-free graphs. V. Global structure , J. Combin. Theory Ser. B 98, 1373-1410 (2008)

    2008

  6. [14]

    Chudnovsky, P

    M. Chudnovsky, P. D. Seymour, Claw-free graphs. VI. Coloring , J. Combin. Theory Ser. B 100, 560-572 (2010)

    2010

  7. [15]

    Chudnovsky, P

    M. Chudnovsky, P. D. Seymour, Claw-free graphs. VII. Quasi-line graphs , J. Combin. The- ory Ser. B 102, 1267-1294 (2012)

    2012

  8. [16]

    Erd˝ os, L

    P. Erd˝ os, L. Lov´ asz,Problems and results on 3-chromatic hypergraphs and some related questions, in Infinite and Finite Sets (Colloq., Keszthely, 1973), Vol. II, Colloq. Math. Soc. J´ anos Bolyai,10, North-Holland, Amsterdam, 609–627 (1975)

    1975

  9. [17]

    Faudree, E

    R. Faudree, E. Flandrin, Z. Ryj´ a˘cek, Claw-free graphs. A survey , Discrete Math. 164, 87-147 (1997)

    1997

  10. [18]

    Fern´ andez, A

    R. Fern´ andez, A. Procacci, Cluster expansions for abstract polymer models. New bounds from an old approach , Comm. Math. Phys. 274, 123-140 (2007)

    2007

  11. [19]

    P. M. S. Fialho, E. Juliano, A. Procacci, A remark on the Whitney Broken Circuit Theorem, to appear in Comput. Appl. Math., doi: 10.1007/s40314-025-03249-0, arXiv:2407.04035 (2024)

    2024 arXiv

  12. [20]

    P. M. S. Fialho, E. Juliano, A. Procacci, On the zero-free region for the chromatic polynomial of graphs with maximum degree ∆ and girth g, preprint arXiv:2409.13892 (2024)

    2024 arXiv

  13. [21]

    I. M. Gessel, B. E. Sagan, The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions, Elect. J. Comb., 3 (2) (The Foata Festschrift volume), Article number R9 (1996)

    1996

  14. [22]

    Jackson, A

    B. Jackson, A. Procacci, A. D. Sokal, Complex zero-free regions at large |q| for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights, J. Comb. Theory Ser. B 103, 21-45 (2013)

    2013

  15. [23]

    Jenssen, V

    M. Jenssen, V. Patel, G. Regts, Improved bounds for the zeros of the chromatic polynomial via Whitney’s Broken Circuit Theorem . J. Combin. Theory Ser. B 169, 233-252 (2024)

    2024

  16. [24]

    Koteck´ y, D

    R. Koteck´ y, D. Preiss, Cluster expansion for abstract polymer models . Commun. Math. Phys. 103, 491-498 (1986). 12

    1986

  17. [25]

    O. J. Heilmann, E. H. Lieb, Theory of monomer-dimer systems , Commun. Math. Phys. 25, no. 3, 190-232 (1972)

    1972

  18. [26]

    J. D. Leake, N. R. Ryder, Generalizations of the Matching Polynomial to the Multivariate Independence Polynomial, Algebr. Comb. 2, 781-802 (2019)

    2019

  19. [27]

    V. E. Levit, E. Mandrescu, A simple proof of an inequality connecting the alternating number of independent sets and the decycling number , Discr. Math. 311, 1204-1206 (2011)

    2011

  20. [28]

    Mantel, Problem 28, soln

    W. Mantel, Problem 28, soln. by H. Gouventak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W.A. Wythoff , Wiskundige Opgaven 10, 60-61 (1907)

    1907

  21. [29]

    G. J. Minty, On maximal independent sets of vertices in claw-free graphs, J. Combin. Theory Ser. B 28 (3), 284-304 (1980)

    1980

  22. [30]

    K. R. Parthasarathy, G. Ravindra, The strong perfect graph conjecture is true for K1,3-free graphs, J. Combin. Theory Ser. B 21, 212-223 (1976)

    1976

  23. [31]

    Patel, P

    A. Patel, P. Regts, Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials . SIAM J. Comput. 48 (6), 1610 -1635 (2019)

    2019

  24. [32]

    Penrose: Convergence of fugacity expansions for classical systems

    O. Penrose: Convergence of fugacity expansions for classical systems. In Statistical mechan- ics: foundations and applications , A. Bak (ed.), Benjamin, New York (1967)

    1967

  25. [33]

    Peters, G

    H. Peters, G. Regts, On a conjecture of Sokal concerning roots of the independence polyno- mial. Michigan Math. J. 68(1) 33-55 (2019)

    2019

  26. [34]

    Procacci, S

    A. Procacci, S. A. Yuhjtman, Convergence of Mayer and virial expansions and the Penrose tree-graph identity, Lett. Math. Phys. 107, 31-46 (2017)

    2017

  27. [35]

    Scott, A

    A. Scott, A. D. Sokal, The repulsive lattice gas, the independent-set polynomial, and the Lov´ asz local lemma, J. Stat. Phys. 118 (5-6), 1151–1261 (2005)

    2005

  28. [36]

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

    1985

  29. [37]

    Whitney, A logical expansion in mathematics, Bull

    H. Whitney, A logical expansion in mathematics, Bull. American Math. Soc. 38 (8), 572-579 (1932). 13

    1932

Pith tools

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