Lemma 30 — weak-separation matching identity
ProvedSpaceReset.Hardness.Supplement.lemma_30graph-theoryinterval-graphsmatchingp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1trellis
Let , , be integer intervals with pairwise distinct starts and pairwise distinct ends. Let be given by (27) and let be the weak-separation graph, in which are adjacent when or . Then
With Lemma 29 and Theorem 8 this identifies the closed memory with a matching deficiency; the proof of Theorem 32 uses it.
Differences from the source:
- encoding: intervals [s_i, t_i] ⊆ [1, n] → s, t : Fin k → ℕ with 1 ≤ s i ≤ t i ≤ n; reason: the same integer intervals, 0-based index i
- encoding: max over 0 ≤ u ≤ v ≤ n of ⌈P(u,v)/2⌉ → the supremum over the base cutPairs n of (P(u,v) + 1) / 2 in ℕ; reason: the same maximum
- encoding: ν(H_G) → the largest size of a set of pairwise disjoint edges of H_G; reason: the matching number
Preamble
import Mathlib import Definitions.Def_SpaceReset_Hardness_Trellis import Definitions.Def_SpaceReset_Hardness_Supplement_Matching set_option autoImplicit false
Formal statement
namespace SpaceReset.Hardness.Supplement
open SpaceReset.Hardness
/-- Lemma 30 (Weak-separation matching identity), App. D.1, p. 42.
For `k` integer intervals `[s_i, t_i] ⊆ [1, n]` with pairwise distinct starts and pairwise
distinct ends, `max_{0 ≤ u ≤ v ≤ n} ⌈P(u,v)/2⌉ = k − ν(H_G)`, with `P` as in (27) and `H_G` the
weak-separation graph. -/
theorem lemma_30 (k n : ℕ) (s t : Fin k → ℕ) (hst : ∀ i, 1 ≤ s i ∧ s i ≤ t i ∧ t i ≤ n)
(hs : Function.Injective s) (ht : Function.Injective t) :
(cutPairs n).sup (fun p => (intervalP s t p.1 p.2 + 1) / 2) =
k - matchingNumber (weakSepGraph s t) := by sorry
end SpaceReset.Hardness.Supplement
Source
Rinka Miura, STOC 2027 submission #1715 (October 2026), The Complexity of Space–Reset Tradeoffs in Online Quantum Computation (held submission, no arXiv version; SHA-256 c2a340e2195da0d130bf10d936d56d4f1d4da805e644efb7fe1c36d9c904f3e5), Lemma 30, p. 42 (App. D.1, (27) on p. 41)