Independent Sets and Continued Fractions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908982879191040 |
|---|---|
| author | Chan, Swee Hong Heilman, Steven Panova, Greta |
| author_facet | Chan, Swee Hong Heilman, Steven Panova, Greta |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_19094 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Independent Sets and Continued Fractions Chan, Swee Hong Heilman, Steven Panova, Greta Combinatorics Number Theory 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. |
| title | Independent Sets and Continued Fractions |
| topic | Combinatorics Number Theory |
| url | https://arxiv.org/abs/2604.19094 |