Inertia, Independence and Expanders
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_ | 1866909664171524096 |
|---|---|
| author | Tang, Quanyu Zhang, Shengtong Elphick, Clive |
| author_facet | Tang, Quanyu Zhang, Shengtong Elphick, Clive |
| contents | Let $G$ be a graph on $n$ vertices, independence number $α(G)$, Lovász theta function $\vartheta(G)$, and Shannon capacity $Θ(G)$. We define $n_{\ge0}(G)$ to be the minimum number of non-negative eigenvalues taken over all Hermitian weighted adjacency matrices of $G$. It is well known that $α(G) \le Θ(G) \le \vartheta(G)$ and $α(G) \le n_{\ge0}(G)$.
Continuing a long line of work, we investigate the relationships between $ α(G) $, $ \vartheta(G) $, $Θ(G)$, and $ n_{\ge 0}(G) $. We prove a conjecture of Kwan and Wigderson, showing that for every integer $k$, there exists a graph $G$ with $α(G) \leq 2$ and $n_{\ge 0}(G) \ge k$. In addition, we prove that for every integer $k$, there exists a graph $G$ with $Θ(G) \leq 3$ and $n_{\ge 0}(G) \ge k$. Both results rely on a new observation: if the complement of $G$ contains a good spectral expander, then $n_{\geq 0}(G)$ must be large. We also show that $\vartheta(G)$ can be exponentially larger than $n_{\ge 0}(G)$, improving a recent result of Ihringer. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_07305 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Inertia, Independence and Expanders Tang, Quanyu Zhang, Shengtong Elphick, Clive Combinatorics Primary 05C50, Secondary 05C35, 05C48, 05C69 Let $G$ be a graph on $n$ vertices, independence number $α(G)$, Lovász theta function $\vartheta(G)$, and Shannon capacity $Θ(G)$. We define $n_{\ge0}(G)$ to be the minimum number of non-negative eigenvalues taken over all Hermitian weighted adjacency matrices of $G$. It is well known that $α(G) \le Θ(G) \le \vartheta(G)$ and $α(G) \le n_{\ge0}(G)$. Continuing a long line of work, we investigate the relationships between $ α(G) $, $ \vartheta(G) $, $Θ(G)$, and $ n_{\ge 0}(G) $. We prove a conjecture of Kwan and Wigderson, showing that for every integer $k$, there exists a graph $G$ with $α(G) \leq 2$ and $n_{\ge 0}(G) \ge k$. In addition, we prove that for every integer $k$, there exists a graph $G$ with $Θ(G) \leq 3$ and $n_{\ge 0}(G) \ge k$. Both results rely on a new observation: if the complement of $G$ contains a good spectral expander, then $n_{\geq 0}(G)$ must be large. We also show that $\vartheta(G)$ can be exponentially larger than $n_{\ge 0}(G)$, improving a recent result of Ihringer. |
| title | Inertia, Independence and Expanders |
| topic | Combinatorics Primary 05C50, Secondary 05C35, 05C48, 05C69 |
| url | https://arxiv.org/abs/2505.07305 |