§3.2, eq. (21) — pathwidth identity [BBJ+25, Lemma 7]
ProvedSpaceReset.Hardness.eq_21graph-theoryp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1pathwidth
For a graph on vertices, let have vertex sets and , each a clique, with an edge exactly when or . Then
This existing identity is the paper's classical input to the reduction.
Differences from the source:
- encoding: pathwidth → GaussianSweep.pathwidth (ℤ-valued, −1 on the empty graph); reason: the standard pathwidth; at N = 0 both sides are −1
Preamble
import Mathlib import Definitions.Def_GaussianSweep_pathwidth import Definitions.Def_SpaceReset_Hardness_Graphs set_option autoImplicit false
Formal statement
namespace SpaceReset.Hardness
/-- §3.2, eq. (21), p. 26: the pathwidth identity [BBJ+25, Lemma 7], `pw(B(X)) = N + pw(X)` for
a graph `X` on `N` vertices. -/
theorem eq_21 (N : ℕ) (X : SimpleGraph (Fin N)) :
GaussianSweep.pathwidth (doubleGraph X) = (N : ℤ) + GaussianSweep.pathwidth X := by sorry
end SpaceReset.Hardness
Source
Rinka Miura, STOC 2027 submission #1715 (October 2026), §3.2, eq. (21), p. 26 (cited: [BBJ+25, Lemma 7])
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.