Sharp Edge-Edit Bounds at Every Level for Leaky Positive Semidefinite Forcing
Abstract
This work disproves the 1-leaky positive semidefinite edge-deletion conjecture and replaces it with a sharp theorem. For every leak level ℓ and edge e, one has |Z+(ℓ)(G)−Z+(ℓ)(G−e)|≤ 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ℓ+1 by a bridge gives Z+(ℓ)(G)=2ℓ and Z+(ℓ)(G−e)=2ℓ+2. For every ℓ≥ 2, a connected clique-leaf pair of order 2ℓ+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.
Related
- On Completely Positive and Semidefinite Programs for Moment Bounds on Maximum of Random Quadratics
- Sharp Antipode-Neighbor Bounds in Every Dimension
- Bricks in which every vertex is incident with a forcing edge
- Near-bipartite bricks in which every b-invariant edge is a forcing edge
- Bounds on the Semidefinite Programming Complexity of the Euclidean Ball
BibTeX
@misc{frijio2026sharp,
title = {{Sharp Edge-Edit Bounds at Every Level for Leaky Positive Semidefinite Forcing}},
author = {Domenico Frijio},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.22804},
eprint = {2609.22804},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.22804},
}
RIS
TY - UNPB
TI - Sharp Edge-Edit Bounds at Every Level for Leaky Positive Semidefinite Forcing
AU - Domenico Frijio
PY - 2026
DA - 2026/09/19
PB - arXiv
DO - 10.48550/arxiv.2609.22804
UR - https://arxiv.org/abs/2609.22804
AB - This work disproves the 1-leaky positive semidefinite edge-deletion conjecture and replaces it with a sharp theorem. For every leak level ℓ and edge e, one has |Z^+_(ℓ)(G)−Z^+_(ℓ)(G−e)|≤ 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_ℓ+1 by a bridge gives Z^+_(ℓ)(G)=2ℓ and Z^+_(ℓ)(G−e)=2ℓ+2. For every ℓ≥ 2, a connected clique-leaf pair of order 2ℓ+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.
ER -