The 2 2 -Quasi-Regularizability Conjecture and Independence Polynomials of đ p \mathbf{W}_{p} Graphs
Kevin Pereyra · 2026
Read The 2 2 -Quasi-Regularizability Conjecture and Independence Polynomials of đ p \mathbf{W}_{p} Graphs by Kevin Pereyra (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14076.txt.
Introduction
Pereyra proves the 2-quasi-regularizability conjecture for Wp graphs. Hoang and co-authors had asked what shape rules make the independence polynomial of a Wp graph log-concave or at least unimodal. They guessed that a connected W2 graph is 2-quasi-regularizable exactly when its order is at least three times its alpha. The proof hinges on a local expansion theorem. Every non-maximum independent set in a connected W2 graph has a neighborhood at least twice its size. Coefficient tests for both traits follow.
Catalog record
| CREATOR | Kevin Pereyra |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32752 |
| LICENSE | http://creativecommons.org/publicdomain/zero/1.0/ |
| RIGHTS | CC0 |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.14076
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The 2 2 -Quasi-Regularizability Conjecture and Independence Polynomials of đ p \mathbf{W}_{p} Graphs Kevin Pereyra Abstract Hoang, Levit, Mandrescu and Pham asked for structural conditions ensuring that the independence polynomial of a đ p \mathbf{W}_{p} graph is log-concave, or at least unimodal, and conjectured that a connected đ 2 \mathbf{W}_{2} graph is 2 2 -quasi-regularizable if and only if n ⥠( G ) â„ 3 â α â ( G ) n(G)\geq 3\alpha(G) (2026). We prove the conjecture. The key point is a local expansion theorem: if G G is connected and belongs to đ 2 \mathbf{W}_{2} , then every non-maximum independent set A A satisfies | N G â ( A ) | â„ 2 â | A | . |N_{G}(A)|\geq 2|A|. Thus the only possible obstruction to 2 2 -quasi-regularizability in a connected đ 2 \mathbf{W}_{2} graph comes from maximum independent sets, where the condition is exactly n ⥠( G ) â α ⥠( G ) â„ 2 â α â ( G ) n(G)-\alpha(G)\geq 2\alpha(G) . We also give coefficient criteria for log-concavity and unimodality of independence polynomials of đ p \mathbf{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 p=2 threshold proved here inserts the missing case into the same framework and yields explicit log-concavity and unimodality regions for connected đ 2 \mathbf{W}_{2} graphs. 2020 MSC 05C69; 05C30; 05C31; 05C35. 1 Introduction Let G be a finite simple graph. Its independence polynomial, introduced by Gutman and Harary [ 10 ] , is I(G;x)=\sum_{k=0}^{\alpha(G)}s_{k}x^{k}, where s_{k} denotes the number of independent sets of cardinality k in G . The sequence (s_{0},s_{1},\ldots,s_{\alpha(G)}) is a natural enumerative invariant of G , but it is far from being constrained in general: Alavi, Malde, Schwenk and Erdos showed that prescribed order patterns can occur among its coefficients [ 1 ] . Nevertheless, important graph classes do force regular behavior. For instance, Heilmann and Liebâs real-rootedness theorem for matching polynomials [ 11 ] , and Chudnovsky and Seymourâs real-rootedness theorem for independence polynomials of claw-free graphs [ 5 ] , both imply log-concavity in their respective settings. Root locations and coefficient questions for independence polynomials have been studied from several viewpoints; see, for example, BrownâHickmanâNowakowski [ 3 ] , the survey of LevitâMandrescu [ 20 ] , and the later work on trees and clique-cover products [ 36 , 37 , 17 ] . The broader role of log-concavity in combinatorics is surveyed by Stanley [ 31 ] , and the modern theory is also influenced by Huhâs work on chromatic and matroidal log-concavity [ 15 , 16 ] . This paper concerns the class \mathbf{W}_{p} introduced by Staples [ 32 , 33 ] . Well-covered graphs originate in the work of Plummer [ 29 , 30 ] ; very well-covered graphs were introduced by Favaron [ 7 ] , and structural results for special well-covered families include [ 8 , 34 ] . A graph is in \mathbf{W}_{p} if every p pairwise disjoint independent sets can be enlarged to p pairwise disjoint maximum independent sets. The class \mathbf{W}_{1} is precisely the class of well-covered graphs. The class \mathbf{W}_{2} is especially important because it coincides, for graphs without isolated vertices, with the class of 1 -well-covered graphs [ 33 , 25 ] ; related \mathbf{W}_{2} subclasses were studied by Pinter [ 28 ] . These graph classes also occur naturally in edge-ideal theory and Gorenstein graph theory [ 35 , 14 ] . On the enumerative side, counterexamples, roller-coaster phenomena and positive results for very well-covered graphs appear in [ 27 , 21 , 24 , 23 , 4 ] . Corona constructions, introduced by Frucht and Harary [ 9 ] , provide a large source of well-covered and \mathbf{W}_{p} examples. In a recent paper, Hoang, Levit, Mandrescu and Pham studied quasi-regularizability and log-concavity for \mathbf{W}_{p} graphs and proved the p -quasi-regularizability threshold for connected \mathbf{W}_{p} graphs when p\neq 2 [ 12 ] . They left the following two questions. Problem 4.1 (HoangâLevitâMandrescuâPham) . What conditions on the \mathbf{W}_{p} graph G guarantee that the independence polynomial I(G;x) is log-concave or at least unimodal? Conjecture 4.2 (HoangâLevitâMandrescuâPham) . Let G be a connected \mathbf{W}_{2} graph. Then G is 2 -quasi-regularizable if and only if n(G)\geq 3\alpha(G). The exclusion of p=2 in the known threshold is not cosmetic. The cycle C_{5} belongs to \mathbf{W}_{2} but is not 2 -quasi-regularizable: if S is a maximum independent set, then |S|=2 and |N(S)|=3<4 . This is exactly the failure of the inequality n(C_{5})\geq 3\alpha(C_{5}) ; see Figure 1 . The main result below proves that this is the only kind of failure. Main structural theorem. Let G be a connected graph in \mathbf{W}_{2} . If A is an independent set which is not maximum, then |N_{G}(A)|\geq 2|A|. Consequently, a connected \mathbf{W}_{2} graph is 2 -quasi-regularizable if and only if n(G)\geq 3\alpha(G) . The proof is local. If a smallest counterexample A existed, then |N(A)|=2|A|-1 . Each vertex of A would have a unique private neighbor; all other neighbors would see at least two vertices of A ; private neighbors would be forced away from the localization G_{A} ; every non-private vertex touching G_{A} would be universal on A ; and finally a second localization would build an augmenting set that contradicts the \mathbf{W}_{2} avoidance property. Figures 4 â 7 show the successive reductions. The local expansion theorem and its application to Conjecture 4.2 are the new structural part of the paper. The coefficient criteria in Section 3 are included to make the consequence for Problem 4.1 self-contained: they combine known two-sided coefficient inequalities with the quasi-regularizability input, and in the case \lambda=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\in\mathbf{W}_{p} , n=n(G) , \alpha=\alpha(G) , and G is \lambda -quasi-regularizable, then the inequalities (k+1)s_{k+1}\leq\bigl(n-(\lambda+1)k\bigr)s_{k},\qquad p(\alpha-k)s_{k}\leq(k+1)s_{k+1} lead to explicit log-concavity and unimodality criteria. The new p=2 threshold supplies the missing quasi-regularizability input exactly when n\geq 3\alpha . v_{1} v_{2} v_{3} v_{4} v_{5} S=\{v_{1},v_{3}\}\in\Omega(C_{5}) N(S)=\{v_{2},v_{4},v_{5}\} \alpha(C_{5})=2 , n(C_{5})=5 |N(S)|=3<2|S|=4 blue: the independent set S orange: its open neighborhood Figure 1: The graph C_{5} is a connected \mathbf{W}_{2} graph, but it is not 2 -quasi-regularizable. The obstruction is a maximum independent set, and 5<3\cdot 2 . The paper is organized as follows. Section 2 fixes the notation and records the standard tools on independence polynomials, quasi-regularizability and \mathbf{W}_{2} graphs. Section 3 proves the coefficient criteria used to answer Problem 4.1. Section 4 proves the local expansion theorem for connected \mathbf{W}_{2} graphs, and Section 5 applies it to Conjecture 4.2. Section 6 derives the corresponding log-concavity and unimodality consequences, and the last section closes with brief remarks. 2 Preliminaries All graphs considered in this paper are finite, undirected, and simple. For undefined graph-theoretic terminology we refer the reader to Diestel [ 6 ] ; for matching terminology we refer to LovĂĄsz and Plummer [ 26 ] . We write V(G) and E(G) for the vertex set and the edge set, n(G)=|V(G)| , and \alpha(G) for the independence number. The family of independent sets is denoted