Lemma 6 — cut localization and both consequences
ProvedContiguousCake597.Approximate.lemma_6cake-cuttingp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1ppad
Let be any nonempty directed graph with every indegree at most two, and use its constructed cake on . Let be any complete -envy-free allocation with real cuts and arbitrary assignment permutation , where , , , and for the number of graph vertices. Every cut, including the endpoints, satisfies
The core is . For player , put , and . Every core is contained in spatial piece , and for every . For every player ,
The overlap length is computed exactly as the nonnegative difference between the smaller upper endpoint and larger lower endpoint. This lemma localizes spatial pieces independently of their recipients.
Differences from the source:
- encoding: one-based pieces and interval intersection length → zero-based Fin indices for pieces and an exact endpoint-overlap formula; reason: the spatial piece with index j in Lean is the paper's piece j+1; cuts retain their numbers, including 0 and N
Preamble
import Definitions.Def_ContiguousCake597_Approximate_Analysis
Formal statement
namespace ContiguousCake597.Approximate
/-- Lemma 6, printed p.9 (PDF 10): every real-cut complete answer,
with arbitrary assignment, satisfies all localization conclusions. -/
theorem lemma_6 (G : HZTractability.ThrGraph) (hn : 1 ≤ G.n)
(hdeg : ∀ v, G.indeg v ≤ 2) (T : Allocation ℝ (N G))
(hT : AnalyticAnswer G T) :
(∀ j : Fin (N G+1), |T.cuts j - (j.val : ℝ) * B G| < 7 * N G) ∧
(∀ j : Fin (N G), core G j ⊆ T.piece j ∧
∀ k : Fin (N G), k ≠ j → T.piece j ∩ core G k = ∅) ∧
(∀ v : Fin G.n,
boundarySet G v ⊆ T.piece (specialPiece G v) ∪ T.piece (followingPiece G v) ∧
overlap (T.cuts (specialPiece G v).castSucc) (T.cuts (specialPiece G v).succ)
((boundary G v).1 : ℝ) ((boundary G v).2 : ℝ) = z G T v) := by sorry
end ContiguousCake597.Approximate
Source
Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui, STOC 2027 submission #597 (October 2026), p. 9 (PDF 10), Lemma 6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.