Tight bounds for positive discrepancy via eigenvalues
Abstract
Given an n× n symmetric matrix M with largest eigenvalue λ1≥ 0, it is easy to show that the solution of the optimisation problem maxv∈ [−1,1]nvTMv is at most λ1 n. We prove the following converse: if every n'× n' principal submatrix of M has maximal eigenvalue at least λ, then maxv∈ [−1,1]nvTMv≥ λ(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+n5/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−Ωε(d1/3n) for d≤ (1−ε)n/2, which is optimal for d=Ω(n). This confirms a conjecture of Räty, Sudakov and Tomon.
Related
- Positive discrepancy of graphs far from Turán graphs
- Sharp bounds for higher mixed Steklov-Robin eigenvalues on domains with holes
- Optimal bounds for embedded eigenvalues of one-dimensional discrete Schrödinger operators with decaying potentials
- Tighter bounds on Komlós discrepancy: existence and algorithmic results
- Positive Eigenvalues of Hadamard Square Roots on Finite Abelian Groups
BibTeX
@misc{janzer2026tight,
title = {{Tight bounds for positive discrepancy via eigenvalues}},
author = {Oliver Janzer and István Tomon and Fredy Yip},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.37961},
eprint = {2609.37961},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37961},
}
RIS
TY - UNPB
TI - Tight bounds for positive discrepancy via eigenvalues
AU - Oliver Janzer
AU - István Tomon
AU - Fredy Yip
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2609.37961
UR - https://arxiv.org/abs/2609.37961
AB - Given an n× n symmetric matrix M with largest eigenvalue λ_1≥ 0, it is easy to show that the solution of the optimisation problem max_v∈ [−1,1]^nv^TMv is at most λ_1 n. We prove the following converse: if every n'× n' principal submatrix of M has maximal eigenvalue at least λ, then max_v∈ [−1,1]^nv^TMv≥ λ(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−Ω_ε(d^1/3n) for d≤ (1−ε)n/2, which is optimal for d=Ω(n). This confirms a conjecture of Räty, Sudakov and Tomon.
ER -