标题： 惯性，独立性和扩张器 显示英文标题

标题： Inertia, Independence and Expanders

摘要： 设 $G$ 是一个具有 $n$ 个顶点的图，独立数为 $\alpha(G)$，洛瓦斯θ函数为 $\vartheta(G)$，香农容量为 $\Theta(G)$。 我们定义 $n_{\ge0}(G)$ 为所有埃尔米特加权邻接矩阵中非负特征值的最小数目，这些矩阵属于 $G$。 众所周知，$\alpha(G) \le \Theta(G) \le \vartheta(G)$和$\alpha(G) \le n_{\ge0}(G)$。 延续长期的研究工作，我们探讨$ \alpha(G) $、$ \vartheta(G) $、$\Theta(G)$和$ n_{\ge 0}(G) $之间的关系。 我们证明了Kwan和Wigderson的一个猜想，表明对于每个整数$k$，存在一个图$G$，使得$\alpha(G) \leq 2$且$n_{\ge 0}(G) \ge k$。 此外，我们证明了对于每个整数$k$，存在一个图$G$具有$\Theta(G) \leq 3$和$n_{\ge 0}(G) \ge k$。 这两个结果都基于一个新的观察：如果$G$的补图包含一个好的谱扩张，则$n_{\geq 0}(G)$必须很大。 我们还证明$\vartheta(G)$可以比$n_{\ge 0}(G)$指数级地更大，改进了Ihringer的最近结果。 显示英文摘要

摘要： Let $G$ be a graph on $n$ vertices, independence number $\alpha(G)$, Lov\'asz theta function $\vartheta(G)$, and Shannon capacity $\Theta(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 $\alpha(G) \le \Theta(G) \le \vartheta(G)$ and $\alpha(G) \le n_{\ge0}(G)$. Continuing a long line of work, we investigate the relationships between $ \alpha(G) $, $ \vartheta(G) $, $\Theta(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 $\alpha(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 $\Theta(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.