Lemma 6.4 — Oriented volume properties
OpenGreedyRegionGrowing.Layouts.Supplement.lemma_6_4combinatoricsgraph-algorithmsoptimizationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Use a weakly connected DAG with n≥2, an optimal rational solution d of (6.1), and any fixed sign at each center whose radius-n/20 oriented ball has at most 3n/4 vertices. For every U and u∈U the oriented volume is a volume function with normalization 2DLP, boundary cost |δ_{G[U]}(B^U(u,r))| and events d(u,x) for source centers or d(x,u) for sink centers. It obeys the bounds below, and removing vertices other than u never increases it. The upper ball-size bound is asserted for positive r≤n/20.
This is a supporting result for Theorem 6.1.
Differences from the source:
- encoding: finite labelled graphs, ordered iterations and polynomial-time algorithms → Fin n carriers, zero-based trace indices, fixed binary codes and deterministic TM2 polynomial time; reason: labels and iteration shifts change no source instance; the codes include all vertices and rational data, and the machine condition records the full runtime claim
Preamble
import Mathlib import Definitions.Def_GreedyRegionGrowing_Layouts_Foundation noncomputable section open Finset QAlgorithms.Complexity
Formal statement
namespace GreedyRegionGrowing.Layouts.Supplement
attribute [local instance] Classical.propDecidable
/-- Finite simple directed graphs (§3): a relation, with acyclicity imposed separately. -/
private abbrev ArcGraph (n : ℕ) := Fin n → Fin n → Prop
private def Acyclic {n : ℕ} (G : ArcGraph n) : Prop :=
(∀ v, ¬ G v v) ∧ ∀ v, ¬ Relation.TransGen G v v
private def arcs {n : ℕ} (G : ArcGraph n) (U : Finset (Fin n)) :=
(U ×ˢ U).filter (fun e => G e.1 e.2)
private def arcCut {n : ℕ} (G : ArcGraph n) (U S : Finset (Fin n)) :=
(arcs G U).filter (fun e => (e.1 ∈ S ∧ e.2 ∉ S) ∨ (e.2 ∈ S ∧ e.1 ∉ S))
private def Topological {n : ℕ} (G : ArcGraph n) (U : Finset (Fin n)) (p : List (Fin n)) : Prop :=
IsOrdering U p ∧ ∀ e ∈ arcs G U, p.idxOf e.1 < p.idxOf e.2
private def storage {n : ℕ} (G : ArcGraph n) (p : List (Fin n)) : ℕ :=
(range (p.length + 1)).sup (fun i => (arcCut G univ (orderingPrefix p i)).card)
private def registers {n : ℕ} (G : ArcGraph n) (p : List (Fin n)) : ℕ :=
(range (p.length + 1)).sup (fun i =>
((orderingPrefix p i).filter (fun u => ∃ v, G u v ∧ v ∉ orderingPrefix p i)).card)
private def MS {n : ℕ} (G : ArcGraph n) : ℕ :=
sInf {k | ∃ p, Topological G univ p ∧ storage G p = k}
private def MRS {n : ℕ} (G : ArcGraph n) : ℕ :=
sInf {k | ∃ p, Topological G univ p ∧ registers G p = k}
private def weightedStorage {n : ℕ} (G : ArcGraph n) (w : Fin n → Fin n → ℚ)
(p : List (Fin n)) : ℚ :=
((List.range (p.length + 1)).map (fun i =>
∑ e ∈ arcCut G univ (orderingPrefix p i), w e.1 e.2)).foldl max 0
private def WMS {n : ℕ} (G : ArcGraph n) (w : Fin n → Fin n → ℚ) : ℝ :=
sInf {r | ∃ p, Topological G univ p ∧ r = (weightedStorage G w p : ℝ)}
private def dagCode {n : ℕ} (G : ArcGraph n) : Str :=
List.replicate n true ++ [false] ++
(List.finRange n).flatMap (fun u => (List.finRange n).map (fun v => decide (G u v)))
private def matrixCode {n : ℕ} (d : Fin n → Fin n → ℚ) : Str :=
(List.finRange n).flatMap (fun u => (List.finRange n).flatMap (fun v => ratCode (d u v)))
private def weightedDagCode {n : ℕ} (G : ArcGraph n) (w : Fin n → Fin n → ℚ) : Str :=
dagCode G ++ (List.finRange n).flatMap (fun u => ((List.finRange n).filter (fun v => decide (G u v))).flatMap (fun v => ratCode (w u v)))
/-- All constraints of (6.1), including the signed empty-set right side. -/
private def DirectedFeasible {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ) : Prop :=
(∀ x y, 0 ≤ d x y) ∧ (∀ x, d x x = 0) ∧
(∀ x y z, d x z ≤ d x y + d y z) ∧
(∀ x y, G x y → d y x = 0) ∧
∀ u (S : Finset (Fin n)), ((S.card : ℚ)^2 - 1)/4 ≤ ∑ v ∈ S, (d u v + d v u)
private def directedObjective {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ) : ℚ :=
∑ e ∈ arcs G univ, d e.1 e.2
private def DirectedOptimal {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ) : Prop :=
DirectedFeasible G d ∧ ∀ d', DirectedFeasible G d' →
directedObjective G d ≤ directedObjective G d'
private def DLP {n : ℕ} (G : ArcGraph n) : ℝ :=
sInf {r | ∃ d, DirectedFeasible G d ∧ r = (directedObjective G d : ℝ)}
private def WeakConnected {n : ℕ} (G : ArcGraph n) : Prop :=
∀ u v, Relation.ReflTransGen (fun x y => G x y ∨ G y x) u v
private def orientedDistance {n : ℕ} (d : Fin n → Fin n → ℚ) (s : Fin n → Bool)
(u v : Fin n) : ℚ := if s u then d u v else d v u
private def orientedBall {n : ℕ} (d : Fin n → Fin n → ℚ) (s : Fin n → Bool)
(U : Finset (Fin n)) (u : Fin n) (r : ℝ) :=
if r ≤ 0 then ∅ else U.filter (fun v => (orientedDistance d s u v : ℝ) < r)
private def SmallSigns {n : ℕ} (d : Fin n → Fin n → ℚ) (s : Fin n → Bool) : Prop :=
∀ u, ((orientedBall d s univ u ((n : ℝ)/20)).card : ℝ) ≤ 3*(n : ℝ)/4
private def directedSetVolume {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
(S : Finset (Fin n)) : ℚ :=
directedObjective G d * S.card / n + ∑ e ∈ arcs G S, d e.1 e.2
private def directedVolume {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
(s : Fin n → Bool) (U : Finset (Fin n)) (u : Fin n) (r : ℝ) : ℝ :=
if r ≤ 0 then 0 else
let B := orientedBall d s U u r
(directedSetVolume G d B : ℝ) +
∑ e ∈ (arcs G U).filter (fun e => if s u then e.1 ∈ B ∧ e.2 ∉ B
else e.1 ∉ B ∧ e.2 ∈ B),
(if s u then r - (d u e.1 : ℝ) else r - (d e.2 u : ℝ))
private def directedVolumeQ {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
(s : Fin n → Bool) (U : Finset (Fin n)) (u : Fin n) (r : ℚ) : ℚ :=
if r ≤ 0 then 0 else
let B := orientedBall d s U u (r : ℝ)
directedSetVolume G d B +
∑ e ∈ (arcs G U).filter (fun e => if s u then e.1 ∈ B ∧ e.2 ∉ B
else e.1 ∉ B ∧ e.2 ∈ B),
(if s u then r - d u e.1 else r - d e.2 u)
private def directedEvents {n : ℕ} (d : Fin n → Fin n → ℚ) (s : Fin n → Bool)
(U : Finset (Fin n)) (u : Fin n) : Finset ℚ := U.image (orientedDistance d s u)
/-- Algorithm 3, operational frame. No performance property is a field. -/
private structure DirectedFrame (n : ℕ) where
U : Finset (Fin n)
rho : ℚ
center : Fin n
radius : ℚ
namespace DirectedFrame
variable {n : ℕ}
private def K (f : DirectedFrame n) (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
(s : Fin n → Bool) : ℚ :=
((f.U.sort (· ≤ ·)).map (fun u => directedVolumeQ G d s f.U u f.rho)).foldl max 0
private def w (f : DirectedFrame n) (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
(s : Fin n → Bool) : ℚ := n * f.K G d s / (320 * directedObjective G d)
private def X (f : DirectedFrame n) (d : Fin n → Fin n → ℚ) (s : Fin n → Bool) :=
orientedBall d s f.U f.center (f.radius : ℝ)
private def W (f : DirectedFrame n) (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
(s : Fin n → Bool) := directedVolume G d s f.U f.center (f.radius : ℝ)
private def nextU (f : DirectedFrame n) (d : Fin n → Fin n → ℚ) (s : Fin n → Bool) :=
f.U \ f.X d s
private def Operational (f : DirectedFrame n) (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
(s : Fin n → Bool) : Prop :=
f.center ∈ f.U ∧
(let a := f.rho - f.w G d s
let E := directedEvents d s f.U f.center
(∀ u ∈ f.U, directedVolumeQ G d s f.U u a ≤ directedVolumeQ G d s f.U f.center a) ∧
a < f.radius ∧ f.radius < f.rho ∧ f.radius ∉ E ∧
∀ r : ℚ, a < r → r < f.rho → r ∉ E →
(arcCut G f.U (f.X d s)).card ≤
(arcCut G f.U (orientedBall d s f.U f.center (r : ℝ))).card)
end DirectedFrame
private def DirectedRunFrom {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
(s : Fin n → Bool) : Finset (Fin n) → ℚ → List (DirectedFrame n) → Prop
| _, _, [] => True
| U, rho, f::fs => f.U = U ∧ f.rho = rho ∧ f.Operational G d s ∧
DirectedRunFrom G d s (f.nextU d s) (rho-f.w G d s) fs
private def DirectedRun {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
(s : Fin n → Bool) (fs : List (DirectedFrame n)) := DirectedRunFrom G d s univ (n/20) fs
private def DirectedComplete {n : ℕ} (d : Fin n → Fin n → ℚ) (s : Fin n → Bool)
(fs : List (DirectedFrame n)) : Prop :=
match fs.getLast? with
| none => n = 0
| some f => f.nextU d s = ∅
private def directedFrameCode {n : ℕ} (f : DirectedFrame n) : Str :=
setCode f.U ++ ratCode f.rho ++ natCode f.center.val ++ ratCode f.radius
private structure DirectedInput where
n : ℕ
G : ArcGraph n
d : Fin n → Fin n → ℚ
s : Fin n → Bool
dag : Acyclic G
connected : WeakConnected G
size : 2 ≤ n
optimal : DirectedOptimal G d
signs : SmallSigns d s
private def directedInputCode (I : DirectedInput) : Str :=
dagCode I.G ++ matrixCode I.d ++ (List.finRange I.n).map I.s
private def DirectedCarvingPolyTime : Prop :=
∃ F : (I : DirectedInput) → List (DirectedFrame I.n),
PPSLattice.PolyTimeOn directedInputCode (fun I => listCode directedFrameCode (F I)) ∧
∀ I, DirectedRun I.G I.d I.s (F I) ∧ DirectedComplete I.d I.s (F I)
private def twoEnded {n : ℕ} (s : Fin n → Bool) (fs : List (DirectedFrame n)) : List (DirectedFrame n) :=
fs.filter (fun f => s f.center) ++ (fs.filter (fun f => !(s f.center))).reverse
/-- Any ordering by contiguous blocks in the required order. -/
private def BlockOrdering {n : ℕ} (d : Fin n → Fin n → ℚ) (s : Fin n → Bool)
(fs : List (DirectedFrame n)) (p : List (Fin n)) : Prop :=
IsOrdering univ p ∧ ∃ blocks : List (List (Fin n)),
blocks.length = fs.length ∧ blocks.flatten = p ∧
∀ i : Fin fs.length, IsOrdering ((fs.get i).X d s) (blocks[i.val]!)
/-- The concrete gadget of Appendix B; minus copies have tag false, plus copies true. -/
private def gadget {n : ℕ} (G : ArcGraph n) : ArcGraph (2*n) := fun x y =>
(∃ v : Fin n, x.val = v.val ∧ y.val = n+v.val) ∨
(∃ u v : Fin n, G u v ∧ x.val = u.val ∧ y.val = v.val) ∨
(∃ u v : Fin n, G u v ∧ x.val = v.val ∧ y.val = n+u.val)
private def gadgetWeight {n : ℕ} (G : ArcGraph n) (x y : Fin (2*n)) : ℚ :=
if ∃ v : Fin n, x.val = v.val ∧ y.val = n+v.val then 1
else 1 / (10 * (arcs G univ).card)
private def restrictMinus {n : ℕ} (p : List (Fin (2*n))) : List (Fin n) :=
p.filterMap (fun x => if h : x.val < n then some ⟨x.val,h⟩ else none)
/-- Aditya Anand, STOC 2027 submission #506 (October 2026), lemma 6 4. -/
theorem lemma_6_4 (I : DirectedInput) (U : Finset (Fin I.n))
(u : Fin I.n) (hu : u ∈ U) :
VolumeFunction (directedVolume I.G I.d I.s U u)
(fun r => (arcCut I.G U (orientedBall I.d I.s U u r)).card)
((directedEvents I.d I.s U u).image (fun q => (q : ℝ))) (2*DLP I.G) ∧
(∀ r, 0 < r → DLP I.G/I.n ≤ directedVolume I.G I.d I.s U u r ∧
directedVolume I.G I.d I.s U u r ≤ 2*DLP I.G) ∧
(∀ U' : Finset (Fin I.n), U' ⊆ U → u ∈ U' → ∀ r, 0 < r →
directedVolume I.G I.d I.s U' u r ≤ directedVolume I.G I.d I.s U u r) ∧
∀ r, 0 < r → r ≤ (I.n : ℝ)/20 →
((orientedBall I.d I.s U u r).card : ℝ) ≤ 3*(I.n : ℝ)/4 := by sorry
end GreedyRegionGrowing.Layouts.Supplement
Source
Aditya Anand, Greedy Region Growing: Improved Approximations for Cutwidth, Pathwidth, Flow-Expander Decomposition, and More, STOC 2027 submission #506 (October 2026). Citation basis: published (canonical held submission); 46 pages; printed page = PDF page throughout (offset 0); no arXiv version. Lemma 6.4, p. 30-31 (PDF p. 30-31).