The stability of independence polynomials of complete bipartite graphs

Bo Ning; Guo Chen; Jianhua Tu

The stability of independence polynomials of complete bipartite graphs

T0 review · 0 major / 5 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 This paper shows complete bipartite graphs split by part-size ratio: near-balanced ones are stable, while those with parts in a fixed ratio greater than 1 are not stable once the smaller part is large enough.

desk verdict A clean, correct answer to Brown–Cameron: near-balanced complete bipartite graphs are stable, linearly unbalanced ones are not, with the only soft spot an external root-location bound quoted for K3,n. read the letter →

arxiv 2505.24381 v1 pith:JWPRGBXT submitted 2025-05-30 math.CO

Guo Chen , Bo Ning , Jianhua Tu This is my paper

classification math.CO MSC 05C3105C69

keywords independencepolynomialsrootsstabilitycompletebipartitegraphsRouché'stheoremlefthalf-planeHurwitzquasi-stablerootlocation

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

The paper targets the open question of whether every complete bipartite graph has a stable independence polynomial, meaning all roots lie in the left half-plane. Its answer is no, with a precise split: $K_{2,n}$ and $K_{3,n}$ are stable for every $n$; $K_{m,m+k}$ is stable for all large $m$ for every fixed integer $k$ (and for all $m$ when $k\le 6$); and for every rational $\ell>1$, $K_{m,\ell m}$ is not stable once $m$ is large. The proofs work with the shifted polynomial $y^n+y^m-1$ and use Rouché's theorem on a fixed rectangle to confine roots, plus a root-modulus argument to force an escaping root in the unbalanced case. If the results are correct, stability of complete bipartite graphs is governed asymptotically by whether the part sizes differ by a bounded additive gap or by a fixed ratio.

What carries the argument

The load-bearing object is the shifted polynomial $\Phi(K_{m,n},y)=y^n+y^m-1$, obtained from $i(K_{m,n},x)=(1+x)^n+(1+x)^m-1$ by $y=1+x$; stability is exactly the condition that every zero of $\Phi$ has $\mathrm{Re}(y)\le 1$. The positive proofs compare $\Phi$ with a simpler polynomial through Rouché's theorem (two analytic functions have equally many zeros inside a contour when one strictly dominates the other on the boundary) on a fixed rectangular contour $\gamma$ with right side $\mathrm{Re}(y)=1$, vertical extent $\pm 2$, and left side $\mathrm{Re}(y)=-3$; on $\gamma$ a strict dominance inequality shows $\Phi$ has as many zeros inside $\gamma$ as the comparison polynomial. For $K_{3,n}$ the comparison polynomial is $-\Phi(K_{1,n},y)$, whose zeros are placed inside $\gamma$ by a cited bound. For the unbalanced direction, the substitution $z=y^r$ with $m=qr$, $\ell=p/q$ reduces $\Phi(K_{m,\ell m},y)$ to $g(z)=z^p+z^q-1$; Vieta's formulas force a zero of $g$ with modulus greater than 1, and taking $r$-th roots spreads it into $r$ zeros spaced by $2\pi/r$, one of which has real part exceeding 1 once $r$ is large.

What would settle it

For $\ell=2$, the proof's construction via the large root of $z^2+z-1$ gives a threshold near $m=20$; computing the roots of $\Phi(K_{21,42},y)=y^{42}+y^{21}-1$ should reveal a root with $\mathrm{Re}(y)>1$, and if every root has $\mathrm{Re}(y)\le1$ the non-stability claim for $K_{m,2m}$ is false.

Watch

Extended reading notes

Core claim

The paper's central discovery is a dichotomy for the independence polynomial $i(K_{m,n},x)=(1+x)^n+(1+x)^m-1$: stability holds for $K_{2,n}$ and $K_{3,n}$ for all $n$, and for $K_{m,m+k}$ once $m$ exceeds a threshold $N(k)$ depending only on $k$; instability holds for $K_{m,\ell m}$ once $m$ exceeds a threshold $N(\ell)$, for every rational $\ell>1$. In the shifted variable $y=1+x$, the positive results mean all roots of $y^n+y^m-1$ satisfy $\mathrm{Re}(y)<1$, and the negative result means some root satisfies $\mathrm{Re}(y)>1$. This settles the previously open 'are all complete bipartite graphs stable?' question in the negative, while showing the failure is confined to graphs whose two parts differ by a fixed factor rather than by a bounded additive gap.

Load-bearing premise

The $K_{3,n}$ proof relies on a cited, not reproved, bound that every root of $y^n+y-1$ lies inside the rectangle $-3\le \mathrm{Re}(y)\le0$, $|\mathrm{Im}(y)|\le2$; if that placement were false, the Rouché comparison would no longer force stability.

Editorial extensions

If this is right

Every complete bipartite graph with a side of size 2 or 3 is stable, extending the known $K_{1,n}$ case.
For any fixed integer gap $k$, all but finitely many $K_{m,m+k}$ are stable; for $k\le 6$ there are no exceptions.
For every rational ratio $\ell>1$, all but finitely many $K_{m,\ell m}$ fail to be stable, so the original question has a negative answer.
The dichotomy is asymptotic in the part-size ratio: a bounded additive gap preserves stability, while a fixed multiplicative gap destroys it once the graph is large.
Each large $K_{m,\ell m}$ admits a specific root with real part exceeding 1, so the non-stability is witnessed by an explicit configuration, not merely by counting.

Reading between the lines

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

The paper proves thresholds $N(k)$ and $N(\ell)$ exist but does not tabulate them; the same contour estimates could be converted into explicit numerical values, and $k=7$ is the first gap where stability fails for small $m$.
An untested middle regime is sublinear imbalance such as $n=m+\lfloor\sqrt{m}\rfloor$: neither a fixed gap nor a fixed ratio, so the two theorems leave its stability undetermined.
One could conjecture from the two regimes that the stability boundary sits at sublinear gaps: $K_{m,n}$ stays stable when $n-m$ is $o(m)$ and fails when $n/m$ stays bounded away from 1, but the paper does not address this.
The threshold $N(\ell)$ depends on the root of $z^p+z^q-1$ of largest modulus, so for explicit rationals such as $\ell=2$ the non-stability witness is computable from the golden-ratio-sized root of $z^2+z-1$.

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.

Desk Editor's Note

read the letter

Punchline: this paper answers the Brown–Cameron question, and it does so with genuinely informative theorems. Theorem 4 gives the negative answer for linearly unbalanced pairs; Theorems 2 and 3 give the positive side for small fixed parts and for near-balanced pairs. None of these are restatements of the K1,n result.

What is good: the proof strategy is uniform and elementary. Rouché's theorem on a fixed rectangle, with boundary inequalities checked case by case, is a convincing way to localize roots. The instability mechanism in Theorem 4—via Vieta, a real root in (0,1), and r-th roots—is clean and gives an explicit N(ℓ). There are no free parameters, no self-citations, and the authors are honest about the k≥7 case, where they only claim stability for m large. I checked the boundary estimates in the K2,n and K3,n proofs; they hold.

The soft spots are minor. The K3,n proof relies on the Brown–Cameron rectangle bound for roots of i(K1,n), quoted as Proposition 2.3 without proof. This is a legitimate citation to a published theorem, but it is the one external load-bearing piece; someone writing a fully self-contained proof would want to fill it in. Also, the c_k values for k≤6 in Theorem 3 are asserted as direct computation; they are easy to verify, but not shown. Neither issue affects the central claims.

The paper leaves the intermediate growth range open (e.g., k growing like m^α with 0<α<1); that is a boundary, not a flaw. The significance is subfield-level: it resolves an open question and gives a clear asymptotic boundary, without reshaping broader combinatorics.

Who gets value: anyone working on independence roots or stable polynomials; the Rouché comparison idea may transfer to other graph families. It deserves a serious referee. I would send it to review with high confidence that the main results are correct.

Referee Report

0 major / 5 minor

Summary. The paper addresses Brown and Cameron's question of whether all complete bipartite graphs are stable, where a graph is stable when all roots of its independence polynomial lie in the closed left half-plane. Working with the translated polynomial Φ(K_{m,n}, y) = y^n + y^m - 1, the authors prove three results: K_{2,n} and K_{3,n} are stable for all n; for every fixed integer k, the nearly balanced graphs K_{m,m+k} are stable for all sufficiently large m (and for k ≤ 6, for all m ≥ 1); and for every rational ℓ > 1, the unbalanced graphs K_{m,ℓm} are not stable for all sufficiently large m when ℓm is an integer. The proofs use Rouché's theorem on a fixed rectangular contour for the first two families, and a Vieta/IVT argument to extract a root of modulus greater than 1 for the unbalanced family. Together these results give a negative answer to Brown and Cameron's question, with a clean dichotomy between nearly balanced and unbalanced complete bipartite graphs.

Significance. If the results are correct, they settle an open question explicitly posed in the literature and provide a sharp qualitative picture: stability is generic for nearly balanced complete bipartite graphs, while sufficiently unbalanced ones are unstable. The main arguments are genuinely self-contained and mathematically transparent: the boundary inequalities in the Rouché proofs are checkable case by case, and the Vieta/intermediate-value construction in Theorem 4 is elegant and contains no fitted parameters or hidden assumptions. The paper is also commendably concrete, giving explicit ranges of stability for small k and an explicit existential threshold for large k. The only external ingredient is the Brown–Cameron root-location bound for K_{1,n} quoted in Proposition 2.3, and the only omitted computational details are the elementary minima c_k in Theorem 3. Neither issue appears to affect the validity of the main claims.

minor comments (5)

[2, Proposition 2.3] The proof of stability of K_{3,n} relies on the quoted Brown–Cameron result that all roots of i(K_{1,n}, x) lie in the interior of the rectangle β. This is the only externally sourced root-location input in Theorem 2, so please state it as a displayed theorem with a precise citation (theorem or lemma number from [1]), or give a short proof, so that the reader can verify the exact hypothesis without consulting the reference.
[3, Proof of Theorem 3] The values of P_k(t) and c_k for k = 2, ..., 6 are asserted by "direct computation" and the inequality c_k > 1 is load-bearing for the claim that K_{m,m+k} is stable for all m ≥ 1 when k ≤ 6. Please include the derivation of these polynomials and their minima, or at least provide a table with the explicit polynomials and the minimizing points.
[3, Proof of Theorem 3] For k ≥ 7 the definition of N(k) uses ln(1/c_k), which is negative if c_k > 1; the preceding sentence "We may assume c_k ≤ 1" covers this, but making this assumption explicit immediately before the definition would avoid confusion.
[4, Proof of Theorem 4] The root t selected by the three tie-breaking rules is unique by construction, but the wording "Let t be the unique root" could be replaced by "Choose t according to the following rules" to make the deterministic nature of the choice clearer.
[1, Introduction] There is a grammatical error in the sentence "This question is interesting as it aim to further our understanding"; it should read "aims".

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main results are derived from Rouché's theorem, Vieta's formulas, and an external root-location theorem, with no fitted parameters or self-citation chains.

full rationale

The paper's derivation chain is self-contained in the sense relevant to circularity: each theorem is proved by explicit analytic arguments that do not assume the conclusion. The proof of Proposition 2.3 uses the cited Brown–Cameron theorem that all roots of i(K1,n,x) lie in the interior of the rectangle beta, then applies Rouché's theorem on the larger contour gamma with f(z) = -Phi(K1,n,z). This is an external mathematical result, not a self-citation, and it is not equivalent to the target statement that K3,n is stable. Theorems 3 and 4 use only Rouché's theorem, polynomial inequalities, Vieta's formulas, and the intermediate value theorem; no parameter is fitted to a subset of data and later renamed a prediction. There is no step where a quantity is defined in terms of the quantity it is supposed to determine, and no uniqueness theorem from the authors' own prior work is invoked. The only potentially load-bearing external dependency is the Brown–Cameron root-location bound for K1,n, which could be a correctness risk if that bound were false or misquoted, but it is not circular: the cited theorem is independent support rather than an assumption of the present paper's main claims. Accordingly, the circularity score is 0.

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

No free parameters are fitted and no new entities are postulated. The proofs rest on standard complex analysis and algebra theorems, on the explicit independence polynomial formula, and on one external root-location theorem for K_{1,n} from Brown and Cameron.

assumptions (5)

standard math Rouché's theorem
Used in Sections 2 and 3 to force roots of the target polynomial inside the rectangular contour γ by comparison with a polynomial with known roots.
standard math Vieta's formulas
Used in Theorem 4 to show the product of moduli of roots of z^p+z^q-1 is 1, forcing a root outside the unit circle.
standard math Intermediate value theorem
Used in Theorem 4 to locate a real root ξ∈(0,1) of g(z)=z^p+z^q-1.
domain assumption Formula i(K_{m,n},x)=(1+x)^n+(1+x)^m-1
Used throughout; it counts independent sets in a complete bipartite graph and defines Φ(K_{m,n},y).
domain assumption Brown-Cameron root-location bound for K_{1,n}
Used in Proposition 2.3 to place all roots of Φ(K_{1,n},y) inside the contour γ; this is cited to [1] and not reproved in the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The stability of independence polynomials of complete bipartite graphs." pith.science (2026). https://pith.science/paper/JWPRGBXT

@misc{pith2026250524381,
  author       = {Pith},
  title        = {Pith review of: The stability of independence polynomials of complete bipartite graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JWPRGBXT}},
  note         = {Machine review of arXiv:2505.24381}
}

abstract

The independence polynomial of a graph is termed {\it stable} if all its roots are located in the left half-plane $\{z \in \mathbb{C} : \mathrm{Re}(z) \leq 0\}$, and the graph itself is also referred to as stable. Brown and Cameron (Electron. J. Combin. 25(1) (2018) \#P1.46) proved that the complete bipartite graph $K_{1,n}$ is stable and posed the question: \textbf{Are all complete bipartite graphs stable?} We answer this question by establishing the following results: \begin{itemize} \item The complete bipartite graphs $K_{2,n}$ and $K_{3,n}$ are stable. \item For any integer $k\geq0$, there exists an integer $N(k)\in \mathbb{N}$ such that $K_{m,m+k}$ is stable for all $m>N(k)$. \item For any rational $\ell> 1$, there exists an integer $N(\ell) \in \mathbb{N}$ such that whenever $m >N(\ell)$ and $\ell \cdot m$ is an integer, $K_{m, \ell \cdot m}$ is \textbf{not} stable. \end{itemize}

Figures

Figures reproduced from arXiv: 2505.24381 by the authors.

**Figure 1.** The curve γ and the closed region it bounds. We now show that |f(z) + g(z)| < |f(z)| for all z ∈ γ. Note that the functions f(z) and g(z) are analytic on the entire complex plane, with |f(z) + g(z)| = 1 and |f(z)| = |z| m · |z + 1|. Thus, we need to show that |z| m · |z + 1| > 1 for all z ∈ γ. It is observed that (1) for any z ∈ γ, |z| ≥ 1, with equality if and only if z = 1, (2) for any z ∈ γ, |z + 1| ≥ 2, with equ… view at source ↗

**Figure 2.** The curve β and the closed region it bounds. Proposition 2.3. The complete bipartite graph K3,n is stable. Proof. We establish the stability of the complete bipartite graph K3,n by demonstrating that if z is a root of Φ(K3,n, x), then Re(z) < 1. By Proposition 2.1, K3,4 is stable. Thus, we assume that n ≥ 5. Let f(z) = −Φ(K1,n, z) = −z n − z + 1 and g(z) = Φ(K3,n, z) = z n + z 3 − 1. Let γ be the curve introduced in… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

Brown, B

J.I. Brown, B. Cameron, On the stability of independence polynomials, Electron. J. Combin. 25 (2018) #P1.46

work page 2018
[2]

Brown, K

J.I. Brown, K. Dilcher, R.J. Nowakowski, Roots of independence polynomials of well- covered graphs, J. Algebraic Combin. 11 (2000) 197–210

work page 2000
[3]

Brown, C.A

J.I. Brown, C.A. Hickman, R.J. Nowakowski, On the location of the roots of inde- pendence polynomials, J. Algebraic Combin. 19 (2004) 273–282

work page 2004
[4]

Brown, R.J

J.I. Brown, R.J. Nowakowski, Average independence polynomials, J. Combin. Theory Ser. B 93 (2005) 313–318

work page 2005
[5]

Choe, J.G

Y.B. Choe, J.G. Oxley, A.D. Sokal, D.G. Wagner, Homogeneous multivariate poly- nomials with the half-plane property, Adv. Appl. Math. 32 (2004) 88–187

work page 2004
[6]

Chudnovsky, P

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

work page 2007
[7]

Csikv´ ari, Note on the smallest root of the independence polynomial, Combin

P. Csikv´ ari, Note on the smallest root of the independence polynomial, Combin. Probab. Comput. 22 (2013) 1–8

work page 2013
[8]

Fisher, Complex Variables, 2nd ed

S.D. Fisher, Complex Variables, 2nd ed. Dover Publications, New York, 1990

work page 1990

Show all 13 references

[9]

Gutman, F

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

1983
[10]

Levit, E

V.E. Levit, E. Mandrescu, The independence polynomial of a graph—a survey, In Proc. 1st Int. Conf. Algebraic Informatics, pages 233–254. Aristotle Univ., Thessa- loniki, 2005

2005
[11]

Wang, B.-X

Y. Wang, B.-X. Zhu, On the unimodality of independence polynomials of some graphs, European J. Combin. 32 (2011) 10–20

2011
[12]

Zhang, X

H. Zhang, X. Hong, Independence polynomials of bipartite graphs, Bull. Malays. Math. Sci. Soc. 45 (2022) 3043–3065

2022
[13]

Zhu, Unimodality of independence polynomials of the incidence product of graphs, Discrete Math

B.-X. Zhu, Unimodality of independence polynomials of the incidence product of graphs, Discrete Math. 341 (2018) 2359–2365

2018

Pith tools

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

[1] [1]

Brown, B

J.I. Brown, B. Cameron, On the stability of independence polynomials, Electron. J. Combin. 25 (2018) #P1.46

work page 2018

[2] [2]

Brown, K

J.I. Brown, K. Dilcher, R.J. Nowakowski, Roots of independence polynomials of well- covered graphs, J. Algebraic Combin. 11 (2000) 197–210

work page 2000

[3] [3]

Brown, C.A

J.I. Brown, C.A. Hickman, R.J. Nowakowski, On the location of the roots of inde- pendence polynomials, J. Algebraic Combin. 19 (2004) 273–282

work page 2004

[4] [4]

Brown, R.J

J.I. Brown, R.J. Nowakowski, Average independence polynomials, J. Combin. Theory Ser. B 93 (2005) 313–318

work page 2005

[5] [5]

Choe, J.G

Y.B. Choe, J.G. Oxley, A.D. Sokal, D.G. Wagner, Homogeneous multivariate poly- nomials with the half-plane property, Adv. Appl. Math. 32 (2004) 88–187

work page 2004

[6] [6]

Chudnovsky, P

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

work page 2007

[7] [7]

Csikv´ ari, Note on the smallest root of the independence polynomial, Combin

P. Csikv´ ari, Note on the smallest root of the independence polynomial, Combin. Probab. Comput. 22 (2013) 1–8

work page 2013

[8] [8]

Fisher, Complex Variables, 2nd ed

S.D. Fisher, Complex Variables, 2nd ed. Dover Publications, New York, 1990

work page 1990