Skip to content
Preprint

Tight bounds for positive discrepancy via eigenvalues

Sep 2026 · 1 citation · 34 references
Mathematics

Abstract

Given an $n\times n$ symmetric matrix $M$ with largest eigenvalue $\lambda_1\geq 0$, it is easy to show that the solution of the optimisation problem $\max_{v\in [-1,1]^n}v^TMv$ is at most $\lambda_1 n$. We prove the following converse: if every $n'\times n'$ principal submatrix of $M$ has maximal eigenvalue at least $\lambda$, then $\max_{v\in [-1,1]^n}v^TMv\geq \lambda(n-n'+1)$. This allows us to lift results about the second largest and the smallest eigenvalue of graphs to the (a priori more difficult) setting of positive discrepancy and MaxCut. Using this new connection, we prove that every $n$-vertex $m$-edge graph that is far from a disjoint union of cliques has a cut of size at least $m/2+n^{5/4-o(1)}$, which is sharp up to the $o(1)$-term. Moreover, we prove that every $d$-regular $n$-vertex graph has bisection width at most $dn/4-\Omega_{\varepsilon}(d^{1/3}n)$ for $d\leq (1-\varepsilon)n/2$, which is optimal for $d=\Omega(n)$. This confirms a conjecture of R\"aty, Sudakov and Tomon.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.