pith. sign in

arxiv: 2605.14076 · v1 · pith:Q4VWJWKOnew · submitted 2026-05-13 · 🧮 math.CO

The 2-Quasi-Regularizability Conjecture and Independence Polynomials of Wp Graphs

Kevin Pereyra This is my paper

Pith reviewed 2026-05-15 02:33 UTC · model grok-4.3

classification 🧮 math.CO
keywords W_p graphsindependence polynomialsquasi-regularizabilitylog-concavityunimodalityindependent setsgraph neighborhoods
0
0 comments X

The pith

A connected W_2 graph is 2-quasi-regularizable exactly when n(G) is at least 3α(G).

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

The paper proves that connected graphs in the W_2 class are 2-quasi-regularizable precisely when the total number of vertices meets or exceeds three times the independence number. This follows from a local expansion result showing that non-maximum independent sets always have neighborhoods at least twice their own size. The only remaining condition is therefore the numerical relation on maximum independent sets. The same quasi-regularizability threshold is then used to obtain explicit criteria for log-concavity and unimodality of the independence polynomials of W_p graphs.

Core claim

We prove that a connected W_2 graph G is 2-quasi-regularizable if and only if n(G) ≥ 3α(G). The key step is the local expansion theorem that |N_G(A)| ≥ 2|A| for every non-maximum independent set A. This reduces the quasi-regularizability question exactly to the inequality on maximum independent sets. Coefficient criteria combining two-sided inequalities with λ-quasi-regularizability then yield log-concavity and unimodality regions for connected W_2 graphs.

What carries the argument

Local expansion theorem for non-maximum independent sets in connected W_2 graphs, requiring |N_G(A)| ≥ 2|A|.

If this is right

  • The obstruction to 2-quasi-regularizability can only arise from maximum independent sets.
  • 2-quasi-regularizability holds exactly when n(G) ≥ 3α(G).
  • Log-concavity and unimodality criteria for independence polynomials are now complete for the W_2 case.
  • The framework for W_p graphs incorporates the p=2 threshold via the same coefficient inequalities.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The expansion bound may hold in other classes with similar neighborhood constraints.
  • Testing the numerical condition on concrete W_2 graphs would verify the equivalence directly.
  • Similar reductions could apply to unimodality questions in related polynomial families.

Load-bearing premise

G is connected and lies in the class W_2.

What would settle it

A counterexample would be any connected W_2 graph where 2-quasi-regularizability and the inequality n ≥ 3α fail to agree.

Figures

Figures reproduced from arXiv: 2605.14076 by Kevin Pereyra.

Figure 1
Figure 1. Figure 1: The graph C5 is a connected W2 graph, but it is not 2-quasi-regularizable. The obstruction is a maximum independent set, and 5 < 3 · 2. the quasi-regularizability input, and in the case λ = p recover the same discriminant range used in [12, Theorem 3.3]. For Problem 4.1 we give a flexible coefficient answer. If G is connected, G ∈ Wp, n = n(G), α = α(G), and G is λ-quasi-regularizable, then the inequalitie… view at source ↗
Figure 2
Figure 2. Figure 2: Localization at an independent set A. The graph GA is obtained by deleting the closed neighborhood NG[A] = A ∪ NG(A) and keeping only the remaining induced subgraph. Definition 2.3 (Independence polynomial, log-concavity, unimodality). Let I(G; x) = αX (G) k=0 skx k = s0 + s1x + · · · + sα(G)x α(G) be the independence polynomial of G, where sk is the number of independent sets of cardinality k. Following [… view at source ↗
Figure 3
Figure 3. Figure 3: The two-sided coefficient inequalities force an initial increasing segment and a final decreasing [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The normal form forced by a smallest hypothetical violation of [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Localizing at A − {x} leaves x with the unique neighbor mx. The leafless property of nontrivial connected W2 graphs forces the whole component to be K2, so mx has no neighbor in H. Suppose, to the contrary, that T ̸= ∅. Consider the localization GT ; see [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The localization GT used in Step 3. If u ∈ U sees H but is not universal on A, then A = R ⊔ T with T ̸= ∅. In GT , the component C contains R, the vertex u, the private neighbors of vertices in R, the vertices of U whose neighbors in A are contained in R, and the part of H touched by u. Step 5: the final localization. Fix an arbitrary vertex x ∈ A and set R = A − {x}. In the localization Gx, the universal … view at source ↗
Figure 7
Figure 7. Figure 7: The final contradiction. After localizing at [PITH_FULL_IMAGE:figures/full_fig_p012_7.png] view at source ↗
read the original abstract

Hoang, Levit, Mandrescu and Pham asked for structural conditions ensuring that the independence polynomial of a $\W_p$ graph is log-concave, or at least unimodal, and conjectured that a connected $\W_2$ graph is $2$-quasi-regularizable if and only if $n(G)\ge 3\alpha(G)$ (2026). We prove the conjecture. The key point is a local expansion theorem: if $G$ is connected and belongs to $\W_2$, then every non-maximum independent set $A$ satisfies \[ |N_G(A)|\ge 2|A|. \] Thus the only possible obstruction to $2$-quasi-regularizability in a connected $\W_2$ graph comes from maximum independent sets, where the condition is exactly $n(G)-\alpha(G)\ge 2\alpha(G)$. We also give coefficient criteria for log-concavity and unimodality of independence polynomials of $\W_p$ graphs. These criteria combine the standard two-sided coefficient inequalities, as collected by Hoang--Levit--Mandrescu--Pham, with $\lambda$-quasi-regularizability. The new $p=2$ threshold proved here inserts the missing case into the same framework and yields explicit log-concavity and unimodality regions for connected $\W_2$ graphs.

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

2 major / 1 minor

Summary. The paper proves the conjecture of Hoang, Levit, Mandrescu and Pham that a connected W_2 graph G is 2-quasi-regularizable if and only if n(G) ≥ 3α(G). The central argument is a local expansion theorem: if G is connected and belongs to W_2, then every non-maximum independent set A satisfies |N_G(A)| ≥ 2|A|. This reduces the only possible obstruction to maximum independent sets, where the condition simplifies to n(G) − α(G) ≥ 2α(G). The paper also supplies coefficient criteria for log-concavity and unimodality of independence polynomials of W_p graphs by combining standard two-sided inequalities with λ-quasi-regularizability, inserting the p=2 case into the existing framework.

Significance. If the reduction step is fully justified, the result resolves the 2-quasi-regularizability conjecture for the connected W_2 case and supplies explicit log-concavity/unimodality regions for these graphs. The direct combinatorial proof via local expansion (with no free parameters or fitted quantities) is a clear strength and completes the structural picture begun in prior work on W_p graphs.

major comments (2)
  1. [paragraph immediately following the local expansion theorem] The reduction from the local expansion theorem to the full if-and-only-if characterization of 2-quasi-regularizability assumes without derivation that |N_G(A)| ≥ 2|A| for every independent set A is equivalent to 2-quasi-regularizability. The manuscript states that the only obstruction comes from maximum independent sets but does not cite or prove the required equivalence (or the precise definition of 2-quasi-regularizability used). This step is load-bearing for the central claim.
  2. [section on coefficient criteria] The coefficient criteria for log-concavity and unimodality are stated to combine the Hoang–Levit–Mandrescu–Pham inequalities with λ-quasi-regularizability, yet the insertion of the new p=2 threshold is not verified against the full set of connected W_2 graphs satisfying n(G) ≥ 3α(G). An explicit check that the resulting coefficient inequalities hold under the proved numerical condition is needed.
minor comments (1)
  1. [abstract and title] The notation W_p versus Wp is used inconsistently in the abstract and title; adopt a single LaTeX macro throughout.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying two points where additional justification would strengthen the manuscript. We address each major comment below and have made the indicated revisions to clarify the central reduction and to supply the requested verification for the coefficient criteria.

read point-by-point responses

  1. Referee: [paragraph immediately following the local expansion theorem] The reduction from the local expansion theorem to the full if-and-only-if characterization of 2-quasi-regularizability assumes without derivation that |N_G(A)| ≥ 2|A| for every independent set A is equivalent to 2-quasi-regularizability. The manuscript states that the only obstruction comes from maximum independent sets but does not cite or prove the required equivalence (or the precise definition of 2-quasi-regularizability used). This step is load-bearing for the central claim.

    Authors: We agree that the equivalence between the neighborhood-expansion condition and 2-quasi-regularizability should be stated explicitly. The definition used in the paper is the one introduced by Hoang, Levit, Mandrescu and Pham: a graph G is 2-quasi-regularizable if it admits a 2-regular spanning multigraph on the same vertex set whose independent sets coincide exactly with those of G. This is known to be equivalent to |N_G(A)| ≥ 2|A| for every independent set A. The local expansion theorem establishes the inequality for all non-maximum independent sets in a connected W_2 graph; the only remaining case is therefore the numerical condition on maximum independent sets, which simplifies to n(G) ≥ 3α(G). We have inserted a short paragraph immediately after the local expansion theorem that recalls this definition, cites the original source, and derives the reduction in one paragraph. This makes the load-bearing step fully explicit while leaving the combinatorial argument unchanged. revision: yes

  2. Referee: [section on coefficient criteria] The coefficient criteria for log-concavity and unimodality are stated to combine the Hoang–Levit–Mandrescu–Pham inequalities with λ-quasi-regularizability, yet the insertion of the new p=2 threshold is not verified against the full set of connected W_2 graphs satisfying n(G) ≥ 3α(G). An explicit check that the resulting coefficient inequalities hold under the proved numerical condition is needed.

    Authors: The coefficient criteria are obtained by substituting the λ-quasi-regularizability parameter into the two-sided inequalities collected by Hoang–Levit–Mandrescu–Pham. Because the local expansion theorem together with the numerical condition n(G) ≥ 3α(G) establishes precisely that every connected W_2 graph is 2-quasi-regularizable, the substitution is valid for the entire class. To make the verification explicit, we have added a brief paragraph in the coefficient-criteria section that confirms the resulting bounds on the independence-polynomial coefficients hold uniformly under the proved condition, using only the expansion property already established. This is a direct (parameter-free) insertion into the existing framework, but the added paragraph addresses the referee’s request for an explicit check. revision: yes

Circularity Check

0 steps flagged

Direct combinatorial proof of external conjecture with no self-referential reduction

full rationale

The paper proves the Hoang-Levit-Mandrescu-Pham conjecture via a local expansion theorem for non-maximum independent sets in connected W_2 graphs, reducing the 2-quasi-regularizability condition to a numerical inequality only on maximum independent sets. This reduction is presented as a logical consequence of the theorem without redefining any quantity in terms of itself, fitting parameters to data then re-deriving them, or relying on load-bearing self-citations. No equations or definitions collapse by construction, and the central claim remains a self-contained combinatorial argument against an external conjecture.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The argument rests on the standard definitions of independent sets, neighborhoods, and the W_p graph class introduced in the cited 2026 paper; no numerical parameters are fitted and no new entities are postulated.

axioms (1)
  • domain assumption Standard definitions of graphs, independent sets, neighborhoods, and the W_p graph family from Hoang–Levit–Mandrescu–Pham (2026).
    The local expansion theorem is proved inside this previously defined class.

pith-pipeline@v0.9.0 · 5537 in / 1402 out tokens · 44321 ms · 2026-05-15T02:33:53.185431+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

37 extracted references · 37 canonical work pages · 2 internal anchors

  1. [1]

    Alavi, P

    Y. Alavi, P. J. Malde, A. J. Schwenk, and P. Erdos,The vertex independence sequence of a graph is not constrained, Congressus Numerantium58(1987), 15–23

    work page 1987

  2. [2]

    Berge,Some common properties for regularizable graphs, edge-critical graphs and B-graphs, Annals of Discrete Mathematics12(1982), 31–44

    C. Berge,Some common properties for regularizable graphs, edge-critical graphs and B-graphs, Annals of Discrete Mathematics12(1982), 31–44

    work page 1982

  3. [3]

    J. I. Brown, C. A. Hickman, and R. J. Nowakowski,On the location of roots of independence polynomials, Journal of Algebraic Combinatorics19(2004), 273–282

    work page 2004

  4. [4]

    Chen and H.-J

    S.-Y. Chen and H.-J. Wang,Unimodality of very well-covered graphs, Ars Combina- toria97A(2010), 509–529

    work page 2010

  5. [5]

    Chudnovsky and P

    M. Chudnovsky and P. Seymour,The roots of the independence polynomial of a claw-free graph, Journal of Combinatorial Theory, Series B97(2007), 350–357

    work page 2007

  6. [6]

    Diestel,Graph Theory, fifth ed., Graduate Texts in Mathematics, vol

    R. Diestel,Graph Theory, fifth ed., Graduate Texts in Mathematics, vol. 173, Springer, Berlin, 2017

    work page 2017

  7. [7]

    Favaron,Very well-covered graphs, Discrete Mathematics42(1982), 177–187

    O. Favaron,Very well-covered graphs, Discrete Mathematics42(1982), 177–187

    work page 1982

  8. [8]

    Finbow, B

    A. Finbow, B. Hartnell, and R. Nowakowski,A characterization of well-covered graphs of girth 5 or greater, Journal of Combinatorial Theory, Series B57(1993), 44–68

    work page 1993

  9. [9]

    Frucht and F

    R. Frucht and F. Harary,On the corona of two graphs, Aequationes Mathematicae4 (1970), 322–324

    work page 1970

  10. [10]

    Gutman and F

    I. Gutman and F. Harary,Generalizations of the matching polynomial, Utilitas Mathematica24(1983), 97–106

    work page 1983

  11. [11]

    O. J. Heilmann and E. H. Lieb,Theory of monomer-dimer systems, Communications in Mathematical Physics25(1972), 190–232

    work page 1972

  12. [12]

    D. T. Hoang, V. E. Levit, E. Mandrescu, and M. H. Pham,Log-concavity of the independence polynomials ofWp graphs, Discrete Mathematics349(2026), no. 8, Article 115109; arXiv:2409.00827v2. DOI: 10.1016/j.disc.2026.115109

    work page doi:10.1016/j.disc.2026.115109 2026

  13. [13]

    D. T. Hoang, V. E. Levit, E. Mandrescu, and M. H. Pham,On the unimodality of the independence polynomial of clique corona graphs, SSRN preprint, available at https://doi.org/10.2139/ssrn.4293649

    work page doi:10.2139/ssrn.4293649

  14. [14]

    D. T. Hoang and T. N. Trung,A characterization of triangle-free Gorenstein graphs and Cohen–Macaulayness of second powers of edge ideals, Journal of Algebraic Combinatorics43(2016), 325–338

    work page 2016

  15. [15]

    Huh,Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs, Journal of the American Mathematical Society25(2012), 907–927

    J. Huh,Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs, Journal of the American Mathematical Society25(2012), 907–927

    work page 2012

  16. [16]

    Huh and E

    J. Huh and E. Katz,Log-concavity of characteristic polynomials and the Bergman fan of matroids, Mathematische Annalen354(2012), 1103–1116. 15

    work page 2012

  17. [17]

    Kadrawi and V

    O. Kadrawi and V. E. Levit,The independence polynomial of trees is not always log-concave starting from order 26, Ars Mathematica Contemporanea25(2025), no. 4, Article P4.03. DOI: 10.26493/1855-3974.3207.2ad

    work page doi:10.26493/1855-3974.3207.2ad 2025

  18. [18]

    Keilson and H

    J. Keilson and H. Gerber,Some results for discrete unimodality, Journal of the American Statistical Association66(334) (1971), 386–389

    work page 1971

  19. [19]

    V.E.LevitandE.Mandrescu,Some operations preserving log-concavity of nonnegative functions, Mathematical Inequalities & Applications9(2006), 63–73

    work page 2006

  20. [20]

    V. E. Levit and E. Mandrescu,The independence polynomial of a graph – a survey, Proceedings of the 1st International Conference on Algebraic Informatics, Aristotle University of Thessaloniki, Greece (2005), 233–254

    work page 2005

  21. [21]

    V. E. Levit and E. Mandrescu,Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture, European Journal of Combi- natorics27(2006), 931–939

    work page 2006

  22. [22]

    V. E. Levit and E. Mandrescu,Very well-covered graphs with log-concave in- dependence polynomials, Carpathian Journal of Mathematics20(2004), 73–80; arXiv:math/0411239

    work page internal anchor Pith review Pith/arXiv arXiv 2004

  23. [23]

    V. E. Levit and E. Mandrescu,Independence polynomials and the unimodality con- jecture for very well-covered, quasi-regularizable, and perfect graphs, inGraph Theory in Paris, Trends in Mathematics, Birkhauser, 2007, 243–254

    work page 2007

  24. [24]

    V. E. Levit and E. Mandrescu,The Roller-Coaster conjecture revisited, Graphs and Combinatorics33(2017), 1499–1508

    work page 2017

  25. [25]

    V. E. Levit and E. Mandrescu,1-well-covered graphs revisited, European Journal of Combinatorics80(2019), 261–272; arXiv:1610.03972

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  26. [26]

    Lovász and M

    L. Lovász and M. D. Plummer,Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, Amsterdam, 1986

    work page 1986

  27. [27]

    T. S. Michael and W. N. Traves,Independence sequences of well-covered graphs: non-unimodality and the Roller-Coaster conjecture, Graphs and Combinatorics19 (2003), 403–411

    work page 2003

  28. [28]

    M. R. Pinter,W2 graphs and strongly well-covered graphs: two well-covered graph subclasses, Ph.D. thesis, Vanderbilt University, 1991

    work page 1991

  29. [29]

    M. D. Plummer,Some covering concepts in graphs, Journal of Combinatorial Theory 8(1970), 91–98

    work page 1970

  30. [30]

    M. D. Plummer,Well-covered graphs: a survey, Quaestiones Mathematicae16(1993), 253–287

    work page 1993

  31. [31]

    R. P. Stanley,Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Annals of the New York Academy of Sciences576(1989), 500–535

    work page 1989

  32. [32]

    J. W. Staples,On some subclasses of well-covered graphs, Ph.D. thesis, Vanderbilt University, 1975. 16

    work page 1975

  33. [33]

    J. W. Staples,On some subclasses of well-covered graphs, Journal of Graph Theory3 (1979), 197–204

    work page 1979

  34. [34]

    Topp and L

    J. Topp and L. Volkmann,On the well-coveredness of products of graphs, Ars Combi- natoria33(1992), 199–215

    work page 1992

  35. [35]

    R. H. Villarreal,Monomial Algebras, Monographs and Textbooks in Pure and Applied Mathematics238, Marcel Dekker, New York, 2001

    work page 2001

  36. [36]

    B. X. Zhu,Clique cover products and unimodality of independence polynomials, Discrete Applied Mathematics206(2016), 172–180

    work page 2016

  37. [37]

    B. X. Zhu and Y. Chen,Log-concavity of independence polynomials of some kinds of trees, Applied Mathematics and Computation342(2019), 35–44. 17

    work page 2019