Metraipolis › archive › dc_ead09bf48c06

Tight bounds for positive discrepancy via eigenvalues — arXiv:2609.37961

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.37961
License (as archived): CC0-1.0
Archived: 2026-10-07T18:33:48.868Z
SHA-256 of the archived text: ad359843bbb92b72a0cdbbc6e87e4253565bebce6e06b28332f74e1ade0b2707
Stable URL of this page: https://metraipolis.com/documento/dc_ead09bf48c06

How to cite

Tight bounds for positive discrepancy via eigenvalues — arXiv:2609.37961 — arXiv (en), https://arxiv.org/abs/2609.37961 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ead09bf48c06 (Metraipolis archive dc_ead09bf48c06, sha256 ad359843bbb92b72a0cdbbc6e87e4253565bebce6e06b28332f74e1ade0b2707)

BibTeX

@misc{dcead09bf48c06,
  title = {Tight bounds for positive discrepancy via eigenvalues — arXiv:2609.37961},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.37961},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ead09bf48c06; sha256 ad359843bbb92b72a0cdbbc6e87e4253565bebce6e06b28332f74e1ade0b2707},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.37961. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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)$. We use this lemma to improve a number of recent results on the MaxCut, bisection width, and discrepancy of graphs. Among others, 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äty, Sudakov and Tomon.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-30 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.37961 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T17:59:19.250Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).