The switching conjecture for main eigenvalues is asymptotically true

Source abstract

An eigenvalue of a signed graph is called \emph{main} if there exists a corresponding eigenvector non-orthogonal to the all-ones vector. An important result of O'Rourke and Touri (2016) states that almost all (unsigned) graphs have all main eigenvalues. Akbari, França, Ghasemian, Javarsineh, and de Lima (2021) considered main eigenvalues of signed graphs and conjectured that for any unsigned connected graph $G \notin\{ K_2, K_4 - e\}$, there is a switching $\mathbf{s}$ such that all eigenvalues of the signed graph $G^{\mathbf{s}}$ are main. We prove two incomparable asymptotic versions of this conjecture. We show that for any graph $G$ of order $n$, there exists a switching $\mathbf{s}\in\{\pm1\}^n$ such that $G^{\mathbf{s}}$ has $n - O\!\left(\frac{n}{(\log n)^{1/4}}\right)$ main eigenvalues counted with multiplicity. Using a similar proof strategy, we also show that if $G$ has $d$ distinct eigenvalues, then there exists a switching $\mathbf{s}\in\{\pm1\}^n$ such that $G^{\mathbf{s}}$ has $d - O\!\left(\frac{d}{(\log d)^{1/4}}\right)$ main eigenvalues.