






















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。