Sharp Edge-Edit Bounds at Every Level for Leaky Positive Semidefinite Forcing

Domenico Frijio

In the authors' words

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) ∣ \leq 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 $ℓ \geq 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.

Main resultThe abstract does not state a limitation.

Sharp Edge-Edit Bounds at Every Level for Leaky Positive Semidefinite Forcing

In the authors' words

More on Combinatorics & discrete math that day

Circular s-choice parking functions: an exact closed formula via rotational symmetry

Single-Fragment Forensic Coding via Multidimensional Cyclically Permutable Codes

The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach

Proof of Almkvist's conjecture on the unimodality of partition polynomials

On infinite families of [Pn​]-irregular graphs

On infinite families of $[P_{n}]$ -irregular graphs