Cardinalities of the total number of independent sets
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912631078518784 |
|---|---|
| author | Kovács, Benedek Nagy, Zoltán Lóránt |
| author_facet | Kovács, Benedek Nagy, Zoltán Lóránt |
| contents | We study the set of numbers the total number of independent sets can admit in $n$-vertex graphs. In this paper, we prove that the cardinality $\mathcal{N}i(n)$ of this set is very close to $2^n$ in the following sense: $\mathcal{N}i(n)/2^n = O(n^{-1/5})$ while for infinitely many $n$, we have $\log_2(\mathcal{N}i(n)/2^n)\ge -2^{(1+o(1)\sqrt{\log_2 n}}$. This set is also precisely the set of possible values of the independence polynomial $I_G(x)$ at $x=1$ for $n$-vertex graphs $G$. As an application, we address an additive combinatorial problem on subsets of a given vector space that avoid certain intersection patterns with respect to subspaces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_24794 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cardinalities of the total number of independent sets Kovács, Benedek Nagy, Zoltán Lóránt Combinatorics 05C69 (Primary) 05C30, 05C31, 05C76, 51E21 (Secondary) We study the set of numbers the total number of independent sets can admit in $n$-vertex graphs. In this paper, we prove that the cardinality $\mathcal{N}i(n)$ of this set is very close to $2^n$ in the following sense: $\mathcal{N}i(n)/2^n = O(n^{-1/5})$ while for infinitely many $n$, we have $\log_2(\mathcal{N}i(n)/2^n)\ge -2^{(1+o(1)\sqrt{\log_2 n}}$. This set is also precisely the set of possible values of the independence polynomial $I_G(x)$ at $x=1$ for $n$-vertex graphs $G$. As an application, we address an additive combinatorial problem on subsets of a given vector space that avoid certain intersection patterns with respect to subspaces. |
| title | Cardinalities of the total number of independent sets |
| topic | Combinatorics 05C69 (Primary) 05C30, 05C31, 05C76, 51E21 (Secondary) |
| url | https://arxiv.org/abs/2505.24794 |