Tight bounds for positive discrepancy via eigenvalues
Given an $n\times n$ symmetric matrix $M$ with largest eigenvalue $λ_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 $λ_1 n$. We prove the following converse: if every $n'\times n'$ principal submatrix of $M$ has maximal eigenvalue at least $λ$, then $\max_{v\in [-1,1]^n}v^TMv\geq λ(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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.37961
curl -X POST /api/v1/records/arxiv/2609.37961/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.37961/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'