Circles and line segments as independence attractors of graphs

Garima Khetawat; Moumita Manna; Tarakanta Nayak

REVIEW 2 major objections 5 minor 1 cited by

Circles and line segments as independence attractors of graphs

T0 review · 2 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 The paper proves that a graph's independence attractor can never be a circle, and that any line-segment independence attractor is one of four intervals $[-4,0]$, $[-2,0]$, $[-\frac{4}{3},0]$, $[-1,0]$.

desk verdict A solid classification of the simplest independence attractors; the main theorem is right, with a patchable n=2 gap and a few assertions that need one more sentence. read the letter →

arxiv 2505.20898 v1 pith:G54OD2JZ submitted 2025-05-27 math.CO math.DS

Garima Khetawat , Moumita Manna , Tarakanta Nayak This is my paper

classification math.COmath.DS MSC 37F2037F1005C6905C31

keywords independencepolynomialattractorfractalJuliasetChebyshevlexicographicproductlinesegmentnumber

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

Independence attractors are the Hausdorff limits of the root sets of the independence polynomials of successive lexicographic powers of a graph. This paper asks which topologically simple sets can occur, and answers with a classification. It proves that a circle is impossible as an independence attractor, and that if an independence attractor is a line segment then the segment is exactly one of $[-4,0]$, $[-2,0]$, $[-\frac{4}{3},0]$, or $[-1,0]$. It then exhibits graphs with independence number four realizing each of these four segments, and shows that the two longest segments require connected graphs. The result matters because it turns a question about limit sets of polynomial roots into a finite list of possible simple shapes, forced by the dynamics of the reduced independence polynomial.

What carries the argument

The machinery is the dynamical system of the reduced independence polynomial $P_G(z)=I_G(z)-1$. Because $I_{G^2}(z)=P_G(P_G(z))+1$, the roots of $I_{G^m}$ are exactly the $m$-th preimages of $-1$ under $P_G$, and their Hausdorff limit is the independence attractor $\mathcal{A}(G)$; this limit equals the Julia set $J(P_G)$ except in the multiple-root case. The decisive tool is conformal conjugacy: when the Julia set is a segment, an affine map $\varphi(z)=az+1$ sends it to $[-1,1]$, and the standard theorem on polynomials with interval Julia set (quoted from the paper's reference [2]) says the conjugate map must be the Chebyshev polynomial $T_n$ or its negative, where $T_0=1$, $T_1=z$, and $T_n=2zT_{n-1}-T_{n-2}$. Coefficient comparison forces $a\in\{\frac12,1,\frac32,2,\frac52\}$, and a triangle-counting inequality for graphs eliminates $a=\frac52$, leaving $a=k/2$ for $k=1,2,3,4$.

What would settle it

Test the missing case directly: the $n=2$, $a=3$ candidate is the reduced independence polynomial $P(z)=4z+6z^2$, which would force a graph on four vertices with six independent pairs. Such a graph would have to be empty and hence have independence number four, not two; so checking all graphs on four vertices with independence number two and verifying none has this polynomial settles whether $[-\frac23,0]$ can occur. A single counterexample graph with this $P$ and independence number two would disprove the theorem's list.

Watch

Extended reading notes

Core claim

The central claim is that simple attractors are maximally restricted. Writing $P_G(z)=I_G(z)-1$ for the reduced independence polynomial, the roots of $I_{G^m}$ are the preimages $P_G^{-m}(-1)$, and when $-1$ is not a super-attracting fixed point these preimage sets converge to the Julia set $J(P_G)$, which is the independence fractal $F(G)$. The paper proves that if $\mathcal{A}(G)$ is a line segment then $\mathcal{A}(G)=F(G)$, so the classification reduces to a dynamical one: polynomials whose Julia set is a line segment. An affine coordinate change sending the segment to $[-1,1]$ makes the polynomial conjugate to a Chebyshev polynomial $T_n$, and coefficient comparisons force the affine parameter to be $k/2$ for $k\in\{1,2,3,4\}$, yielding $\mathcal{A}(G)=[-\frac{4}{k},0]$. A circle is ruled out because a circular Julia set forces the graph to be empty, whose attractor is the singleton $\{-1\}$, while the multiple-root case would make the attractor a disjoint union rather than a circle. The paper closes by constructing graphs with independence number four for each allowed segment.

Load-bearing premise

The classification assumes that every polynomial whose Julia set is a line segment is affinely conjugate to a Chebyshev polynomial, and inside that chain it applies the inequality $6^{n-1}<\binom{n^2}{n}$ to rule out $a=3$ even though the inequality is proved only for $n>2$, leaving the $n=2$ case unhandled.

Editorial extensions

If this is right

If $\mathcal{A}(G)$ is a line segment, it is one of $[-4,0]$, $[-2,0]$, $[-\frac43,0]$, or $[-1,0]$; no segment of any other length appears.
Whenever the attractor is a line segment, it coincides with the independence fractal and with the Julia set of $P_G$, so the graph's independence dynamics is conjugate to a Chebyshev polynomial and the graph has $n^2$ vertices for some $n$.
No disconnected graph has independence attractor $[-4,0]$ or $[-2,0]$, so any realization of those two segments must be connected.
There are at least 325 two-component disconnected graphs whose independence attractor is $[-1,0]$, and at least ten whose attractor is $[-\frac43,0]$, all with independence number four.
A circle can appear as an independence fractal for an empty graph, but the attractor of that graph is the single point $\{-1\}$, so circles cannot survive the passage from fractal to attractor.

Reading between the lines

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

The affine-conjugacy step is purely analytic, so the four-segment list likely applies to any polynomial with positive integer coefficients, zero constant term, and $P'(0)>1$ whose Julia set is a segment; only the graph-realization checks restrict the independence number.
The proof rules out $a=3$ using the bound $6^{n-1}<\binom{n^2}{n}$, which is proved only for $n>2$. The $n=2$ candidate would give the segment $[-\frac23,0]$; the paper does not explicitly show that no graph with independence number two realizes the corresponding polynomial $4z+6z^2$, so this is a small gap in the exclusion.
If the $n=2$ case were eventually realized, the theorem's list would need a fifth segment, $[-\frac23,0]$; if it is not, a short coefficient argument (six independent pairs on four vertices would force an empty graph) closes the gap.
The same method suggests that any other Jordan curve, such as an ellipse, would require a reduced independence polynomial conjugate to a map other than a power or Chebyshev map, so simple non-circular curves may be hard to realize as attractors.

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

Two things: the paper completes a natural classification — independence attractors cannot be circles, and if an attractor is a line segment it must be [-4/k, 0] for k = 1, 2, 3, 4. This genuinely extends Barik et al.'s alpha=3 result to all independence numbers, and the Chebyshev-conjugacy approach fits the problem well. The main theorem B is believable and, as far as I followed the coefficient comparisons, correct.

What is new: Theorem A and Theorem B are not in Brown et al. or Barik et al. Theorem C provides graphs with independence number four realizing each of the four segments and proves that no disconnected graph realizes k = 1 or 2. The exclusion of a = 5/2 via the Nordhaus-Stewart triangle-counting inequality is a nice use of a nonstandard tool, and Lemma 8's inequality is elementary.

Soft spots: the n = 2 case of Theorem B is indeed missing in the written argument. Lemma 8 is only stated for n > 2, and the proof invokes it to rule out a = 3. The stress-test note is right that this is a missing sentence rather than a broken theorem: for n = 2, a = 3 forces the graph to be empty on four vertices, whose independence number is 4, not 2. So the theorem survives, but the paper should patch that paragraph explicitly. Lemma 8's proof also skips n = 6; the inequality is true there, so this is cosmetic. The no-circle proof asserts, without proof, that a Julia set strictly contained in a circle forces the Fatou set to be connected and to be the basin of infinity. That statement is true — a proper closed subset of a circle does not separate the plane — but it needs a sentence.

A separate weakness is that Theorem C's examples for k = 1 and 2 are provided only as figures, and the counts in Lemma 10 are figure-dependent. That is a reproducibility issue, not a mathematical one, but it will make verification harder for referees.

The citation pattern is fine: the paper builds on Brown et al. and Hickman's thesis, extends Barik et al., and self-citation is limited to background context.

Who this is for: people working on independence polynomials, graph attractors, or Julia sets of polynomials with nonnegative integer coefficients. It deserves a serious referee. I would accept it conditionally, with the request to fix the n = 2 argument, add the Fatou-connectedness justification, and ideally make the example graphs available as explicit edge lists.

Referee Report

2 major / 5 minor

Summary. The paper studies the possible topological shapes of the independence attractor A(G), defined as the Hausdorff limit of the root sets of the independence polynomials of iterated lexicographic powers of G. Using the relation between A(G) and the Julia set of the reduced independence polynomial P_G, the authors prove that no independence attractor is a circle (Theorem A), that if A(G) is a line segment then it must be [-4/k,0] for some k in {1,2,3,4} (Theorem B), and that for each such k there is a graph with independence number four realizing that segment (Theorem C). They also prove that A(G)=F(G) whenever A(G) is a line segment.

Significance. The main results give a complete classification of two simple topological types for independence attractors: circles are impossible and line segments are restricted to four explicit intervals. The proofs combine classical rigidity results for polynomial Julia sets (Beardon's theorems and Chebyshev polynomials) with elementary graph-counting inequalities, and the paper supplies explicit graphs realizing all four segments. The reproduction of the foundational identities and the detailed case analysis in Section 4 are useful. Once the small proof gaps noted below are filled, this will be a solid reference for further work on independence attractors.

major comments (2)

[§3.2, proof of Theorem B] The exclusion of a=3 is incomplete for n=2. Lemma 8 is stated only for n>2, and at n=2 the inequality becomes equality, 6=binom(4,2). The written proof therefore does not eliminate the candidate segment [-2/3,0] for a graph with independence number two. A separate argument is needed; for example, a=3 forces a2=binom(4,2), so the graph on 4 vertices has no edges and hence independence number 4, contradicting n=2. Please add this case explicitly.
[§3.1, proof of Theorem A] In the multiple-root case, the sentence 'This means that, the Fatou set is connected and is the attracting domain corresponding to ∞' is asserted without proof. The needed fact is that a proper closed subset of a circle has connected complement in the plane; since ∞ lies in the Fatou set, the unique Fatou component must be the attracting basin of ∞. This justification should be added, as the contradiction depends on it.

minor comments (5)

[§3.2, Lemma 8] The proof verifies n=3,4,5 and n>6 but omits n=6; add the direct check 6^5 < binom(36,6).
[§3.1, Lemma 3] In the statement 'φPφ^{-1}(z)=βz^n, for some β∈C with |α|=1', the symbol α should be β.
[§3.2, proof of Theorem B] The step 'By Lemma 9, q^{n−1} divides 2^{n−1}' is not a direct application of Lemma 9 as stated, since gcd(q,2p) need not be 1. The conclusion is correct but should be justified by unique factorization: every prime dividing q must divide 2, and the exponent forces q=1 or 2.
[Theorem B] The statement of Theorem B should specify that 'line segment' means a non-degenerate segment; otherwise singleton attractors such as {0} for complete graphs and {-1} for empty graphs are excluded by the claimed list.
[§4, Lemma 10] The phrase 'each of its vertex has degree at most' should read 'each of its vertices has degree at most'.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity; the one self-citation is not load-bearing and the main classification rests on external theorems.

full rationale

The paper's central Theorems A and B are derived from external complex-dynamics facts: Beardon's classification of polynomials with a circle or interval as a completely invariant set ([2], Theorems 1.3.1 and 1.4.1), the identification of the independence fractal with the Julia set of P_G ([2], [3]), and Theorem 2.9 from Hickman's thesis [4]. The candidate values k in {1,2,3,4} emerge from coefficient divisibility and the inequality in Lemma 8, not from any fitted parameter or from the definition of the independence attractor. The one self-citation is [1], which shares author T. Nayak; it is cited in the introduction for the prior independence-number-three classification and for examples realizing the four segments, but the proof of Theorem B does not invoke [1], and Theorem C supplies its own independence-number-four examples. Thus the self-citation is not load-bearing. The n=2 omission in Lemma 8 is a genuine proof gap: the lemma is stated for n>2 but is used to exclude a=3 without a separate n=2 argument, yet this is a correctness issue rather than circularity, and the exclusion can be patched by noting that a1=4 and a2=6 force the empty graph on 4 vertices, whose reduced independence polynomial has degree 4, not 2. No fitted-input, self-definitional, or author-imported uniqueness step occurs.

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

The paper does not introduce new postulates; it relies on classical complex dynamics (Beardon's classification theorems and backward-iteration convergence) and the known equality between the independence fractal and the Julia set of the reduced independence polynomial. The proof gap for n = 2 is a gap in deduction, not an added axiom.

assumptions (4)

standard math For a polynomial of degree n with Julia set the unit circle, the map is conjugate to z -> beta z^n for some beta with |beta| = 1 (Beardon, Theorem 1.3.1).
Used in Lemma 3 to classify graphs whose independence fractal is a circle.
standard math For a polynomial with Julia set [-1, 1], the polynomial is conjugate to ±T_n via an affine map (Beardon, Theorem 1.4.1).
Used in Theorem B to force the reduced independence polynomial to be an affine conjugate of a Chebyshev polynomial.
standard math For a polynomial of degree at least two, if z0 is neither attracting periodic nor in a Siegel disk, then lim f^{-m}(z0) = J(f) in the Hausdorff metric (Theorem 2.6, from Beardon via [3]).
This is the central tool linking preimages of -1 to the Julia set; used in Theorem 2.9 and subsequent proofs.
domain assumption F(G) = J(P_G) for every graph G different from K1 (Theorem 2.7, from [3]).
Connects the independence fractal to the Julia set of the reduced independence polynomial; used throughout.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Circles and line segments as independence attractors of graphs." pith.science (2026). https://pith.science/paper/G54OD2JZ

@misc{pith2026250520898,
  author       = {Pith},
  title        = {Pith review of: Circles and line segments as independence attractors of graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G54OD2JZ}},
  note         = {Machine review of arXiv:2505.20898}
}

abstract

By an independent set in a simple graph $G$, we mean a set of pairwise non-adjacent vertices in $G$. The independence polynomial of $G$ is defined as $I_G(z)=a_0 + a_1 z + a_2 z^2+\cdots+a_\alpha z^{\alpha}$, where $a_i$ is the number of independent sets in $G$ with cardinality $i$ and $\alpha$ is the cardinality of a largest independent set in $G$, known as the independence number of $G$. Let $G^m$ denote the $m$-times lexicographic product of $G$ with itself. The independence attractor of $G$, denoted by $\mathcal{A}(G)$, is defined as $\mathcal{A}(G) = \lim_{m\rightarrow \infty} \{z: I_{G^m}(z)=0\}$, where the limit is taken with respect to the Hausdorff metric on the space of all compact subsets of the plane. This paper deals with independence attractors that are topologically simple. It is shown that $\mathcal{A}(G)$ can never be a circle. If $\mathcal{A}(G)$ is a line segment then it is proved that the line segment is $[-\frac{4}{k}, 0]$ for some $k \in \{1, 2, 3, 4 \}$. Examples of graphs with independence number four are provided whose independence attractors are line segments.

Figures

Figures reproduced from arXiv: 2505.20898 by the authors.

**Figure 3.** Complement of G5 5. Let G5 be a connected graph such that IG5 (z) = 1 + 13z + 21z 2 + 9z 3 . Then the complement of G5 has 13 vertices, 21 edges and 9 triangles. Further, each of its vertex has degree at most 11. Figure (3) provides such a graph. Four more non-isomorphic graphs with the same independence polynomial as that of G5 can be obtained by replacing the edges v4v6 and v4v7 by (i) v4v7, v4v10, (ii) v4v1, v4v5… view at source ↗

**Figure 4.** Twenty five possibilities for the complement of [PITH_FULL_IMAGE:figures/full_fig_p021_4.png] view at source ↗

Figures from the paper (1 more)

**Figure 5.** Figure 5: Complement of G′ [PITH_FULL_IMAGE:figures/full_fig_p022_5.png]

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Structural Classification of a Graph with Independence Number Five
math.CO 2026-07 reject novelty 4.0 of 10

The paper enumerates the possible independence polynomials of disconnected graphs with independence number five and line-segment independence attractor.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages · cited by 1 Pith paper

[1]

Barik, T

S. Barik, T. Nayak and A. Pradhan, Graphs whose Independence fractals are line segments, Bull. Malays. Math. Sci. Soc. 44, 55–78 (2021)

work page 2021
[2]

Alikhani and Y

S. Alikhani and Y. Peng, Independence roots and independence fractals of certain graphs, J. Appl. Math. Comput., 36 (1-2), 89--100, (2011)

work page 2011
[3]

A. F. Beardon, Iteration of Rational Functions, Springer-Verlag, New York, (1991)

work page 1991
[4]

Beaton, J

I. Beaton, J. I. Brown and B. Cameron, Independence equivalence classes of paths and cycles, Australas. J. Combin., 75, 127--145, (2019)

work page 2019
[5]

Bollobas, Modern Graph Theory, Springer, New York, (1998)

B. Bollobas, Modern Graph Theory, Springer, New York, (1998)

work page 1998
[6]

J. I. Brown, C. A. Hickman and R. J. Nowakowski, The independence fractal of a graph, J. Comb. Theory, Ser. B, 87, 209--230, (2003)

work page 2003
[7]

C. A. Hickman, Roots of chromatic and independence polynomials, Ph.D. Thesis, Dalhousie University, (2001)

work page 2001
[8]

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

work page 2004

Show all 15 references

[9]

Chudnovsky and P

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

2007
[10]

Csikvari, Note on the Smallest Root of the Independence Polynomial, Combinatorics, Probability and Computing, 22(1), 1--8, (2013)

P. Csikvari, Note on the Smallest Root of the Independence Polynomial, Combinatorics, Probability and Computing, 22(1), 1--8, (2013)

2013
[11]

Gutman and F

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

1983
[12]

Zhang, A way to construct independence equivalent graphs, Appl

H. Zhang, A way to construct independence equivalent graphs, Appl. Math. Lett., 25(10), 1304--1308, (2012)

2012
[13]

J. P. Boyd, Chebyshev and fourier spectral methods, Dover Publications, (2001)

2001
[14]

J. R. Munkres, Topology, Prentice Hall, Inc., NJ, (2000)

2000
[15]

E. A. Nordhaus, and B. M. Stewart,Triangles in an ordinary graph, Canadian J. Math., 15, 33--41, (1963)

1963

Pith tools

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

[1] [1]

Barik, T

S. Barik, T. Nayak and A. Pradhan, Graphs whose Independence fractals are line segments, Bull. Malays. Math. Sci. Soc. 44, 55–78 (2021)

work page 2021

[2] [2]

Alikhani and Y

S. Alikhani and Y. Peng, Independence roots and independence fractals of certain graphs, J. Appl. Math. Comput., 36 (1-2), 89--100, (2011)

work page 2011

[3] [3]

A. F. Beardon, Iteration of Rational Functions, Springer-Verlag, New York, (1991)

work page 1991

[4] [4]

Beaton, J

I. Beaton, J. I. Brown and B. Cameron, Independence equivalence classes of paths and cycles, Australas. J. Combin., 75, 127--145, (2019)

work page 2019

[5] [5]

Bollobas, Modern Graph Theory, Springer, New York, (1998)

B. Bollobas, Modern Graph Theory, Springer, New York, (1998)

work page 1998

[6] [6]

J. I. Brown, C. A. Hickman and R. J. Nowakowski, The independence fractal of a graph, J. Comb. Theory, Ser. B, 87, 209--230, (2003)

work page 2003

[7] [7]

C. A. Hickman, Roots of chromatic and independence polynomials, Ph.D. Thesis, Dalhousie University, (2001)

work page 2001

[8] [8]

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

work page 2004