Lemma 1 — refining P_{k−1}(G) by small (<k)-out sets
ProvedDirKECC1549.Main.lemma_1directed-graphsedge-connectivitygraph-algorithmsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1word-ram
There are one deterministic word-RAM program and one absolute constant with the following property. Let be a directed multigraph with vertices and edges, and let , be integers. Started on the graph layout of , with in the parameter cells and labels of the partition into -edge-connected components in the input array, the program halts within
ticks and outputs labels of a partition that
- is a refinement of ;
- preserves every -edge-connected component of ;
- separates every pair of vertices that are -edge-connected but not -connected.
Lemma 1 handles all cuts below in which one side has out-volume at most in or in .
Formalization Note The input labels are words in cells , equal exactly for -edge-connected vertices; the output labels are words in cells , and relates iff their output words are equal.
Differences from the source:
- generalization: directed graph with parallel edges (p.9) → self-loops also allowed; reason: a loop leaves no vertex set and can be deleted from any path, so it changes no out_D, no λ_D and no component; on loop-free multigraphs the statement is exactly the source's
- encoding: vertex set V and edge multiset E → vertices Fin n, edge ids Fin m, an edge map Fin m → Fin n × Fin n; reason: Lean convention; parallel edges are distinct ids, so every count includes multiplicities as on p.9; same instances
- encoding: edge-disjoint directed paths; λ_D(u,v) ≥ k → pairwise edge-disjoint trails (walks using no edge id twice); λ ≥ k as "k such trails exist"; reason: edge-disjoint walks shorten to edge-disjoint paths, so the counts agree
- encoding: running time on the word-RAM (p.25) → ticks of the published word-RAM WordRAM.run (Hagerup's model, multiplication instruction set, one tick per instruction, no native constants); reason: the paper's model is the standard word-RAM; every instruction costs one tick
- encoding: O(·) with explicit dependence on k → one program for all k (k read from memory) and one absolute constant c fixed before every input; reason: an O(·) without subscript hides an absolute constant; the k-dependence is written out
- generalization: a word-RAM call with word size Θ(log N) → the contract holds for every memory content outside the stated cells and for every word width w with 2^w at least the algorithm's capacity C(N+1)^D+N+16 at the layout size N; reason: Hagerup's model does not initialize memory, and a subroutine runs inside a larger program's width; it specializes to the standard setting
- reading: Lemma 1's input G and P_{k−1}(G), with an O(2^k (k+1)! nΔ) bound that has no m term → the graph layout of G and Gᴿ and labels of P_{k−1}(G) are already in memory; reason: the bound is sublinear in m, so the graph must already be represented; Lemma 5's proof charges O(m) separately (p.18)
- encoding: a directed graph G → n ≥ 1; reason: nondegeneracy: at n = 0 the bound is 0 and no program halts in 0 ticks; it excludes only the empty graph
- encoding: the partitions P_{k−1}(G) and P → per-vertex label words, two vertices in one block iff their words are equal; reason: output convention of §5.3, p.26; same content
Preamble
import Mathlib import Definitions.Def_DirKECC1549_Main_Machine import Definitions.Def_DirKECC1549_Main_Alg3 set_option autoImplicit false open WordRAM
Formal statement
namespace DirKECC1549.Main
/-- Lemma 1, p.11. One deterministic word-RAM program with one absolute constant `c`: for every
multigraph `G` with `n ≥ 1` vertices and integers `k ≥ 2`, `Δ ≥ k − 1`, given the graph layout,
`k`, `Δ` and labels of the partition `P_{k−1}(G)` into `(k−1)`-edge-connected components, it
outputs, within `c·2^k·(k+1)!·n·Δ` ticks, labels of a partition `P` that refines `P_{k−1}(G)`,
preserves every `k`-edge-connected component of `G`, and separates every pair of vertices that
are `(k−1)`-edge-connected but not `(k, Δ)`-connected. -/
theorem lemma_1 :
∃ (A : Complexity.Algorithm .multiplication) (c : ℝ), 0 < c ∧
∀ (n m : ℕ) (G : Fin m → Fin n × Fin n) (k Δ : ℕ),
1 ≤ n → 2 ≤ k → k - 1 ≤ Δ →
Implements A (8 * blk n m + k + Δ)
(fun _ mem => GraphLayout G mem ∧ (mem (paramCell n m 0)).toNat = k ∧
(mem (paramCell n m 1)).toNat = Δ ∧
∀ u v : Fin n, labelRel mem (arrayCell n m 0) u v ↔ KEdgeConnected (k - 1) G u v)
(c * 2 ^ k * ((k + 1).factorial : ℝ) * n * Δ)
(fun _ mem => Refines (labelRel mem (outCell n m 0)) (KEdgeConnected (k - 1) G) ∧
PreservesKECC k G (labelRel mem (outCell n m 0)) ∧
∀ u v, KEdgeConnected (k - 1) G u v → ¬ KDeltaConnected k Δ G u v →
¬ labelRel mem (outCell n m 0) u v) := by sorry
end DirKECC1549.Main
Source
Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas, Charis Papadopoulos, Christos Pergaminelis, STOC 2027 submission #1549 (October 2026), Section 3.1, Lemma 1, p.11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.