arxiv: 2604.19094 · v1 · submitted 2026-04-21 · 🧮 math.CO · math.NT

Recognition: unknown

Independent Sets and Continued Fractions

Swee Hong Chan , Steven Heilman , Greta Panova

Authors on Pith no claims yet

Pith reviewed 2026-05-10 02:46 UTC · model grok-4.3

classification 🧮 math.CO math.NT

keywords independent setstreesplanar graphscontinued fractionsZaremba's conjecturegrowth exponentasymptotic densityphase transition

0 comments

The pith

The numbers of independent sets realized by trees have a lower growth exponent of 0.1966, connected planar graphs realize almost all positive integers, and edge density determines whether every positive integer is hit.

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

Linek's 1989 question asked whether independent-set counts of trees miss infinitely many positive integers. The paper establishes a positive lower growth exponent of 0.1966 for the realized counts, showing the missed numbers become relatively sparse. It proves that connected planar graphs achieve asymptotic density one among all positive integers. It further identifies a sharp phase transition: graphs whose average degree stays below 1 miss a density-one set of integers, while graphs whose average degree is bounded by some fixed D realize every positive integer.

Core claim

The set of integers that arise as the number of independent sets in a tree has lower growth exponent 0.1966. The set of integers that arise as the number of independent sets in a connected planar graph has asymptotic density one. For any d less than 1 the independent-set counts of graphs with fewer than d times vertices edges form a density-zero set, yet there exists a constant D such that every positive integer arises as the independent-set count of some graph with at most D times vertices edges.

What carries the argument

The translation of bounded-partial-quotient continued-fraction expansions (via Shkredov's resolution of a case of Zaremba's conjecture) into explicit graphs whose independent-set counts equal any prescribed positive integer.

If this is right

The independent-set counts of trees are dense enough that their counting function grows at least like n to the power 0.1966.
Connected planar graphs are already rich enough to realize a density-one subset of all positive integers.
Independent-set realizability undergoes a genuine threshold phenomenon controlled by average degree: sublinear density misses almost everything, while linear density above a fixed threshold hits everything.

Where Pith is reading between the lines

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

The same continued-fraction technique may extend to other graph parameters such as matching counts or chromatic polynomials.
It is now natural to ask for the smallest possible D and whether the transition occurs exactly at average degree 1.
Computational enumeration of small trees and planar graphs could test whether the predicted gaps appear at the scales suggested by the exponent 0.1966.

Load-bearing premise

That the continued-fraction solutions supplied by Shkredov's work can be turned into concrete graphs, without planarity or connectivity obstructions, whose independent-set numbers exactly match every positive integer.

What would settle it

An explicit integer larger than any fixed bound that cannot be realized as the number of independent sets in any graph whose number of edges is at most D times its number of vertices, for the D furnished by the construction.

Figures

Figures reproduced from arXiv: 2604.19094 by Greta Panova, Steven Heilman, Swee Hong Chan.

**Figure 1.** Figure 1: A planar graph obtained by consecutive gluing operations in Proposition 4.1. Each “triangle” is an instance of a G′ graph and the marked vertices are on the bottom line. The corresponding continued fraction is [2, 3, 4, 2, 1, 5, . . .]. It follows readily that (G′′, v′′) is a marked planar graph satisfying a(G ′′, v′′) = b(G, v), b(G ′′, v′′) = a(G, v) + i(G ′ − v ′ − w ′ )b(G, v). Therefore it follows tha… view at source ↗

**Figure 2.** Figure 2: The graph H for the case k = 5 in Proposition 4.1. The final constructed graph G starts with a single vertex (corresponding to (1, 1) ∈ Z) and then performs ℓ gluing operations corresponding to k taking the values a1, . . . , aℓ in (4.2). Also observe that |V (G′ )| ≤ 5 in each of the three cases described above. Since the Euclidean algorithm terminates in at most ℓ ≤ logϕ q steps for any given q, our cons… view at source ↗

read the original abstract

Linek's 1989 problem asks whether the numbers of independent sets of trees avoid infinitely many positive integers. We show that the set of natural numbers realized as the number of independent sets of a tree has a lower growth exponent of $0.1966$. We further prove that the set of positive integers representable by connected planar graphs has asymptotic density one. Lastly, we establish a phase transition: the number of independent sets of graphs with fewer than $d|V|$ edges for any $d<1$ is contained in a set of density zero, whereas, following Shkredov's recent breakthrough on Zaremba's conjecture in continued fraction theory, there exists a constant $D$ such that the number of independent sets of graphs with at most $D|V|$ edges covers all positive integers.

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.

Desk Editor's Note private letter to a colleague

The paper gives a 0.1966 lower growth exponent for independent-set counts on trees, shows density one for connected planar graphs, and proves a phase transition at linear edge density using Shkredov's Zaremba result.

read the letter

The punchline is that this work makes the image of the independent-set function on trees grow at least like n^0.1966 and shows that connected planar graphs realize a density-one set of positive integers. It also pins down a sharp threshold: below average degree 2 the realized numbers have density zero, but for some fixed D the graphs with at most D times vertices edges hit every positive integer, by importing Shkredov's recent density result on bounded partial quotients in continued fractions.

Referee Report

1 major / 1 minor

Summary. The paper addresses Linek's 1989 question on which positive integers arise as the number of independent sets in a tree. It proves that the realized set has lower growth exponent at least 0.1966. It further shows that the positive integers arising as independent-set counts of connected planar graphs have asymptotic density one. Finally, it establishes a phase transition: for any d < 1 the independent-set counts of graphs with fewer than d|V| edges lie in a density-zero set, while (invoking Shkredov's resolution of a case of Zaremba's conjecture) there exists a constant D such that graphs with at most D|V| edges realize every positive integer.

Significance. If the constructions are correct, the results give the first quantitative lower bound on the growth of the tree-independent-set spectrum and the first density-one statement for planar graphs, together with a sharp threshold on average degree for full coverage. The explicit link to bounded-partial-quotient continued fractions is a notable strength.

major comments (1)

The phase-transition claim (abstract and the section invoking Shkredov's theorem) asserts that every positive integer is realized by some graph with average degree at most D. The manuscript must supply an explicit, uniform construction that maps each bounded-quotient continued fraction to a concrete graph (or family of graphs) whose independence polynomial evaluates exactly to the target integer while keeping the total number of edges ≤ D|V|. Without this mapping and a verification that no extraneous independent sets are introduced by the gadgets, the covering statement does not follow from the number-theoretic density result alone.

minor comments (1)

The abstract states the three main theorems cleanly; the introduction should include a short roadmap indicating where each proof appears and which auxiliary results (e.g., the 0.1966 exponent construction) are self-contained versus dependent on external theorems.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and valuable feedback on our manuscript. The major comment raises an important point about the completeness of the argument linking continued fractions to graph constructions in the phase-transition result. We address this below and will revise the manuscript accordingly.

read point-by-point responses

Referee: The phase-transition claim (abstract and the section invoking Shkredov's theorem) asserts that every positive integer is realized by some graph with average degree at most D. The manuscript must supply an explicit, uniform construction that maps each bounded-quotient continued fraction to a concrete graph (or family of graphs) whose independence polynomial evaluates exactly to the target integer while keeping the total number of edges ≤ D|V|. Without this mapping and a verification that no extraneous independent sets are introduced by the gadgets, the covering statement does not follow from the number-theoretic density result alone.

Authors: We agree that the current exposition does not provide a sufficiently explicit and uniform construction to make the implication fully rigorous. While the manuscript establishes a connection between independent-set counts and continued fractions with bounded partial quotients, it does not include the detailed gadget-based mapping, verification that the independence polynomial evaluates precisely to the target integer, or an explicit check that the average degree remains bounded by a constant D independent of the target integer. In the revised version we will add a dedicated subsection containing: (i) a uniform, recursive construction associating to each continued fraction with partial quotients at most A a concrete graph G; (ii) a proof that the number of independent sets of G equals the desired positive integer (the denominator of the convergent); and (iii) a verification that the gadgets introduce no extraneous independent sets and that |E(G)| ≤ D|V(G)| for a fixed D. This will ensure that Shkredov's density result directly yields the claimed covering statement for graphs of bounded average degree. revision: yes

Circularity Check

0 steps flagged

No significant circularity; results rely on external theorem and direct constructions

full rationale

The paper's claims on the lower growth exponent for independent-set counts of trees and the asymptotic density for connected planar graphs are presented as arising from direct constructions or analytic arguments. The phase-transition statement explicitly invokes Shkredov's independent resolution of a case of Zaremba's conjecture as an external input rather than deriving coverage internally or via self-citation chains. No self-definitional reductions, fitted parameters renamed as predictions, ansatzes smuggled through citations, or uniqueness theorems imported from the authors' prior work appear in the derivation chain. The cited result is treated as an independent number-theoretic fact that is then translated into graph constructions, leaving the central claims self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper works inside standard ZFC set theory and the usual definitions of graphs, trees, and planar graphs; the only external non-standard input is Shkredov's theorem on Zaremba's conjecture, which is treated as a black-box result rather than re-derived.

axioms (1)

standard math Standard axioms of graph theory and asymptotic density in the integers
Invoked throughout the statements on growth exponents and asymptotic density.

pith-pipeline@v0.9.0 · 5426 in / 1284 out tokens · 51446 ms · 2026-05-10T02:46:30.847344+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

28 extracted references · 8 canonical work pages

[1]

Noga Alon, Matija Buci \'c , and Lior Gishboliner, The spanning tree spectrum: improved bounds and simple proofs, 2025, preprint, 9 pp., arXiv:2503.23648 https://arxiv.org/abs/2503.23648, to appear in Proceedings of the American Mathematical Society

work page arXiv 2025
[2]

Noga Alon, Simi Haber, and Michael Krivelevich, The number of f -matchings in almost every tree is a zero residue, The Electronic Journal of Combinatorics 18 (2011), P30, 10 pp

2011
[3]

102, Amer

Ian Agol and Vyacheslav Krushkal, Structure of the flow and Yamada polynomials of cubic graphs, Breadth in contemporary topology, Proceedings of Symposia in Pure Mathematics, vol. 102, Amer. Math. Soc., Providence, RI, 2019, pp. 1–-20

2019
[4]

Malde, Allen J

Yousef Alavi, Paresh J. Malde, Allen J. Schwenk, and Paul Erd o s, The vertex independence sequence of a graph is not constrained, Congressus Numerantium 58 (1987), 15--23

1987
[5]

2, 423--448

Ferenc Bencs, Pjotr Buys, and Han Peters, The limit of the zero locus of the independence polynomial for bounded degree graphs, Michigan Mathematical Journal 75 (2025), no. 2, 423--448

2025
[6]

1, 137--196

Jean Bourgain and Alex Kontorovich, On Z aremba's conjecture , Annals of Mathematics 180 (2014), no. 1, 137--196

2014
[7]

Jean Bourgain, Partial quotients and representation of rational numbers, Comptes Rendus Mathematique 350 (2012), 727--730

2012
[8]

Swee Hong Chan, Alex Kontorovich, and Igor Pak, Spanning trees and continued fractions, 2024, preprint, 21 pp., arXiv:2411.18782 https://arxiv.org/abs/2411.18782

work page arXiv 2024
[9]

, Effective resistance in planar graphs and continued fractions, 2025, preprint, 10 pp., arXiv:2505.19168 https://arxiv.org/abs/2505.19168

work page arXiv 2025
[10]

114776, 19 pp

Swee Hong Chan and Igor Pak, Computational complexity of counting coincidences, Theoretical Computer Science 1015 (2024), no. 114776, 19 pp

2024
[11]

Kang, The hard-core model in graph theory, 2025, preprint, 35 pp., arXiv:2501.03379 https://arxiv.org/abs/2501.03379

Ewan Davies and Ross J. Kang, The hard-core model in graph theory, 2025, preprint, 35 pp., arXiv:2501.03379 https://arxiv.org/abs/2501.03379

work page arXiv 2025
[12]

David Galvin, Trees with non log-concave independent set sequences, 2025, preprint, 10 pp., arXiv:2502.10654 https://arxiv.org/abs/2502.10654

work page arXiv 2025
[13]

1, 52--72

Catherine Greenhill, The complexity of counting colourings and independent sets in sparse graphs and hypergraphs, Computational Complexity 9 (2000), no. 1, 52--72

2000
[14]

3, 294--309

Steven Heilman, Independent sets of random trees and sparse random graphs, Journal of Graph Theory 109 (2025), no. 3, 294--309

2025
[15]

1, 9--45

Doug Hensley, A polynomial time algorithm for the H ausdorff dimension of continued fraction C antor sets , Journal of Number Theory 58 (1996), no. 1, 9--45

1996
[16]

Michael Han, Sycamore Herlihy, Kirsti Kuenzel, Daniel Martin, and Rachel Schmidt, The number of independent sets in bipartite graphs and benzenoids, Aequationes Mathematicae 99 (2025), 1175--1195

2025
[17]

Shin Yih Huang, An improvement to Z aremba's conjecture , Geometric and Functional Analysis 25 (2015), 860--914

2015
[18]

Hiu-Fai Law, On the number of independent sets in a tree, The Electronic Journal of Combinatorics 17 (2010), N18, 5 pp

2010
[19]

, On the number of f -matchings in a tree, The Electronic Journal of Combinatorics 19 (2012), P43, 11 pp

2012
[20]

2, 131--136

Václav Linek, Bipartite graphs can have any number of independent sets, Discrete Mathematics 76 (1989), no. 2, 131--136

1989
[21]

2, A25, 11 pp

Florian Luca and Carl Pomerance, Irreducible radical extensions and euler-function chains, Integers 7 (2007), no. 2, A25, 11 pp

2007
[22]

Rafael Miyazaki, Cosmin Pohoata, and Michael Zheng, Chromatic polynomial evaluation spectra, 2025, preprint, 20 pp., arXiv:2512.19600 https://arxiv.org/abs/2512.19600

work page arXiv 2025
[23]

Eric Ramos and Sunny Sun, An AI enhanced approach to the tree unimodality conjecture , 2025, preprint, 35 pp., arXiv:2510.18826 https://arxiv.org/abs/2510.18826

work page arXiv 2025
[24]

On some results of K orobov and L archer and Z aremba's conjecture

Ilya D. Shkredov, On some results of K orobov and L archer and Z aremba's conjecture , 2026, preprint, 36 pp., arXiv:2603.14116 https://arxiv.org/abs/2603.14116

work page arXiv 2026
[25]

287--296

Allan Sly, Computational transition at the uniqueness threshold, Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2010, pp. 287--296

2010
[26]

Wagner, Almost all trees have an even number of independent sets, The Electronic Journal of Combinatorics 16 (2009), no

Stephan G. Wagner, Almost all trees have an even number of independent sets, The Electronic Journal of Combinatorics 16 (2009), no. 1, R93, 10 pp

2009
[27]

140--149

Dror Weitz, Counting independent sets up to the tree threshold, Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), 2006, pp. 140--149

2006
[28]

Stanis aw K. Zaremba, La m\'ethode des ``bons treillis'' pour le calcul des int\'egrales multiples, Applications of number theory to numerical analysis, Academic Press, New York-London, 1972, pp. 39--119

1972