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.