Metraipolis › archive › dc_d1194c5ccdb1

Sharp Edge-Edit Bounds at Every Level for Leaky Positive Semidefinite Forcing — arXiv:2609.22804

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.22804
License (as archived)
CC0-1.0
Archived
2026-10-09T21:44:41.221Z
SHA-256 of the archived text
3cc840112dba5dde2c23155e6e6fe115ff9c65e117e02a58d46a510d5ee958be
Stable URL of this page
https://metraipolis.com/documento/dc_d1194c5ccdb1

How to cite

Sharp Edge-Edit Bounds at Every Level for Leaky Positive Semidefinite Forcing — arXiv:2609.22804 — arXiv (en), https://arxiv.org/abs/2609.22804 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d1194c5ccdb1 (Metraipolis archive dc_d1194c5ccdb1, sha256 3cc840112dba5dde2c23155e6e6fe115ff9c65e117e02a58d46a510d5ee958be)
BibTeX
@misc{dcd1194c5ccdb1,
  title = {Sharp Edge-Edit Bounds at Every Level for Leaky Positive Semidefinite Forcing — arXiv:2609.22804},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.22804},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d1194c5ccdb1; sha256 3cc840112dba5dde2c23155e6e6fe115ff9c65e117e02a58d46a510d5ee958be},
  year = {2026}
}

Archived text

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

This work disproves the 1-leaky positive semidefinite edge-deletion conjecture and replaces it with a sharp theorem. For every leak level $\ell$ and edge $e$, one has $|Z^+_{(\ell)}(G)-Z^+_{(\ell)}(G-e)|\le 2$. More generally, if two graphs differ only on edges with both endpoints in $S$, their parameters differ by at most $|S|$. An endpoint-sensitive refinement recovers an increase of at most one whenever some minimum set for $G-e$ contains an endpoint of $e$. Both signs are sharp for every positive leak level. Joining two copies of $K_{\ell+1}$ by a bridge gives $Z^+_{(\ell)}(G)=2\ell$ and $Z^+_{(\ell)}(G-e)=2\ell+2$. For every $\ell\ge 2$, a connected clique-leaf pair of order $2\ell+3$ gives the opposite difference. The remaining positive-difference one-leak case is attained by connected graphs on nine vertices with $Z^+_{(1)}(H)=4$ and $Z^+_{(1)}(G)=6$. Explicit forcing sequences, fort certificates, and an exact verifier check the finite extremal example and stress-test the general results.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.22804 — 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-09T21:26:41.099Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).