Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Submodular width, clique embedding power, fractional (X,Y)(X,Y)(X,Y)-separators, (μ,λ)(\mu,\lambda)(μ,λ)-connectivity and the hub inequality

Definition
SparseIncidenceHom_WidthComparison_Supplement_Widths

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

clique-embeddingshypergraphsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1submodular-widthwidth-parameters

Let HHH be a finite hypergraph (no empty edges, every vertex in an edge) with primal graph P(H)P(H)P(H).

  1. A function b:2V(H)→R≥0b:2^{V(H)}\to\mathbb R_{\ge0}b:2V(H)→R≥0​ is an edge-dominated polymatroid if b(∅)=0b(\varnothing)=0b(∅)=0, b(X)≤b(Y)b(X)\le b(Y)b(X)≤b(Y) for X⊆YX\subseteq YX⊆Y, b(X∪Y)+b(X∩Y)≤b(X)+b(Y)b(X\cup Y)+b(X\cap Y)\le b(X)+b(Y)b(X∪Y)+b(X∩Y)≤b(X)+b(Y), and b(e)≤1b(e)\le1b(e)≤1 for every hyperedge eee. The submodular width is
subw⁡(H)=sup⁡b min⁡(T,B) max⁡t∈V(T)b(B(t)),\operatorname{subw}(H)=\sup_{b}\ \min_{(T,B)}\ \max_{t\in V(T)} b(B(t)),subw(H)=bsup​ (T,B)min​ t∈V(T)max​b(B(t)),

the supremum over edge-dominated polymatroids taken outside the minimum over tree decompositions.

  1. Two nonempty sets U,W⊆V(H)U,W\subseteq V(H)U,W⊆V(H) touch if they intersect or some hyperedge meets both. A clique embedding ψ:Km→H\psi:K_m\to Hψ:Km​→H assigns to each i∈[m]i\in[m]i∈[m] a nonempty set ψ(i)\psi(i)ψ(i) that is connected in P(H)P(H)P(H), with ψ(i)\psi(i)ψ(i) and ψ(j)\psi(j)ψ(j) touching whenever i≠ji\ne ji=j (images may coincide). Its weak edge depth and the clique embedding power are
d(ψ)=max⁡e∈E(H)∣{i∈[m]:ψ(i)∩e≠∅}∣,emb⁡(H)=sup⁡m≥3, ψ:Km→Hmd(ψ).d(\psi)=\max_{e\in E(H)}|\{i\in[m]:\psi(i)\cap e\ne\varnothing\}|,\qquad \operatorname{emb}(H)=\sup_{m\ge3,\ \psi:K_m\to H}\frac{m}{d(\psi)}.d(ψ)=e∈E(H)max​∣{i∈[m]:ψ(i)∩e=∅}∣,emb(H)=m≥3, ψ:Km​→Hsup​d(ψ)m​.

On the empty hypergraph no embedding exists and emb⁡=0\operatorname{emb}=0emb=0.

  1. For a nonnegative vertex weighting μ\muμ write μ(X)=∑v∈Xμ(v)\mu(X)=\sum_{v\in X}\mu(v)μ(X)=∑v∈X​μ(v). A fractional (X,Y)(X,Y)(X,Y)-separator is a nonnegative hyperedge weighting sss such that every path PPP of P(H)P(H)P(H) from a vertex of XXX to a vertex of YYY satisfies ∑e: e∩V(P)≠∅s(e)≥1\sum_{e:\,e\cap V(P)\ne\varnothing}s(e)\ge1∑e:e∩V(P)=∅​s(e)≥1. A set WWW is (μ,λ)(\mu,\lambda)(μ,λ)-connected if for all disjoint X,Y⊆WX,Y\subseteq WX,Y⊆W every fractional (X,Y)(X,Y)(X,Y)-separator has ∑es(e)≥λmin⁡{μ(X),μ(Y)}\sum_e s(e)\ge\lambda\min\{\mu(X),\mu(Y)\}∑e​s(e)≥λmin{μ(X),μ(Y)}.

  2. A pseudometric on [k][k][k] is d:[k]×[k]→R≥0d:[k]\times[k]\to\mathbb R_{\ge0}d:[k]×[k]→R≥0​ with d(i,i)=0d(i,i)=0d(i,i)=0, d(i,j)=d(j,i)d(i,j)=d(j,i)d(i,j)=d(j,i) and d(i,j)≤d(i,l)+d(l,j)d(i,j)\le d(i,l)+d(l,j)d(i,j)≤d(i,l)+d(l,j); distinct points may be at distance 000. For nonempty A,BA,BA,B, d(A,B)=min⁡i∈A,j∈Bd(i,j)d(A,B)=\min_{i\in A,j\in B}d(i,j)d(A,B)=mini∈A,j∈B​d(i,j). A constant CCC satisfies the hub inequality (10) if for every k≥2k\ge2k≥2 and every pseudometric ddd on [k][k][k] some z∈[k]z\in[k]z∈[k] has

∑u∈[k]d(z,u)≤Clog⁡kmax⁡∅≠A,B⊆[k]A∩B=∅min⁡{∣A∣,∣B∣} d(A,B).\sum_{u\in[k]}d(z,u)\le C\log k\max_{\substack{\varnothing\ne A,B\subseteq[k]\\ A\cap B=\varnothing}}\min\{|A|,|B|\}\,d(A,B).u∈[k]∑​d(z,u)≤Clogk∅=A,B⊆[k]A∩B=∅​max​min{∣A∣,∣B∣}d(A,B).

These are the objects of Section 6, which connect unbounded submodular width to W[1]-hardness through clique embeddings.

Formalization Note Logarithms are to base two (the published logTwo). Tree decompositions and the minimum over them are the published optimalWidth. Paths are Mathlib walks with IsPath; a hyperedge counts once if it meets the path's vertex set. [k][k][k] is Fin k.

Definition code
import Mathlib
import Definitions.Def_SparseIncidenceHom_WidthComparison_Decompositions

namespace SparseIncidenceHom.WidthComparison.Supplement

open SparseIncidenceHom.WidthComparison

/-- p. 8. An edge-dominated polymatroid: `b : 2^V → ℝ≥0`, `b(∅) = 0`, monotone, submodular, and
`b(e) ≤ 1` for every hyperedge `e`. -/
def IsEdgeDominatedPolymatroid {V : Type} (H : FiniteHypergraph V) (b : Set V → ℝ) : Prop :=
  (∀ X, 0 ≤ b X) ∧ b ∅ = 0 ∧ (∀ X Y, X ⊆ Y → b X ≤ b Y) ∧
  (∀ X Y, b (X ∪ Y) + b (X ∩ Y) ≤ b X + b Y) ∧ ∀ e : Edge H, b e.val ≤ 1

/-- p. 8. Submodular width: supremum over edge-dominated polymatroids OUTSIDE the minimum over
tree decompositions, exactly as the published `adaptiveWidth` with modular weights. -/
noncomputable def submodularWidth {V : Type} [Fintype V] (H : FiniteHypergraph V) : ℝ :=
  sSup {c | ∃ b : Set V → ℝ, IsEdgeDominatedPolymatroid H b ∧ c = optimalWidth H b}

/-- p. 20. A nonempty vertex set that is connected in the primal graph `P(H)`. -/
def IsConnectedSet {V : Type} (H : FiniteHypergraph V) (S : Set V) : Prop :=
  S.Nonempty ∧ ∀ u ∈ S, ∀ v ∈ S, ∃ p : (primal H).Walk u v, ∀ w ∈ p.support, w ∈ S

/-- p. 20. Two sets touch if they intersect or some hyperedge meets both. -/
def Touch {V : Type} (H : FiniteHypergraph V) (U W : Set V) : Prop :=
  (U ∩ W).Nonempty ∨ ∃ e ∈ H.graph.edgeSet, (e ∩ U).Nonempty ∧ (e ∩ W).Nonempty

/-- p. 20. A clique embedding `ψ : K_m → H`: nonempty connected images, pairwise touching for
distinct clique vertices; images may coincide. -/
structure CliqueEmbedding {V : Type} (H : FiniteHypergraph V) (m : ℕ) where
  img : Fin m → Set V
  connected : ∀ i, IsConnectedSet H (img i)
  touch : ∀ i j, i ≠ j → Touch H (img i) (img j)

/-- Equation (8): the weak edge depth `d(ψ) = max_e |{i : ψ(i) ∩ e ≠ ∅}|`. -/
noncomputable def weakEdgeDepth {V : Type} [Fintype V] {H : FiniteHypergraph V} {m : ℕ}
    (ψ : CliqueEmbedding H m) : ℕ := by
  classical
  exact Finset.univ.sup (fun e : Edge H =>
    (Finset.univ.filter (fun i : Fin m => (ψ.img i ∩ e.val).Nonempty)).card)

/-- Equation (8): the clique embedding power `emb(H) = sup_{m ≥ 3, ψ : K_m → H} m / d(ψ)`.
On the empty hypergraph no embedding exists and the value is `sSup ∅ = 0`. -/
noncomputable def cliqueEmbeddingPower {V : Type} [Fintype V] (H : FiniteHypergraph V) : ℝ :=
  sSup {c | ∃ (m : ℕ) (ψ : CliqueEmbedding H m), 3 ≤ m ∧ c = (m : ℝ) / (weakEdgeDepth ψ : ℝ)}

/-- p. 24. `μ(X) = ∑_{v ∈ X} μ(v)`. -/
noncomputable def weightOf {V : Type} (μ : V → ℝ) (X : Finset V) : ℝ := ∑ v ∈ X, μ v

/-- p. 24. A fractional `(X, Y)`-separator: a nonnegative hyperedge weighting `s` such that every
path of `P(H)` from a vertex of `X` to a vertex of `Y` meets hyperedges of total weight at least 1
(a hyperedge counts once if it meets the path's vertex set). -/
noncomputable def IsFractionalXYSeparator {V : Type} [Fintype V] (H : FiniteHypergraph V)
    (X Y : Set V) (s : Edge H → ℝ) : Prop := by
  classical
  exact (∀ e, 0 ≤ s e) ∧ ∀ x ∈ X, ∀ y ∈ Y, ∀ p : (primal H).Walk x y, p.IsPath →
    1 ≤ ∑ e : Edge H, if (∃ w ∈ p.support, w ∈ e.val) then s e else 0

/-- p. 24. `W` is `(μ, λ)`-connected: for all disjoint `X, Y ⊆ W`, every fractional
`(X, Y)`-separator has total weight at least `λ · min{μ(X), μ(Y)}`. -/
def IsMuLambdaConnected {V : Type} [Fintype V] (H : FiniteHypergraph V) (μ : V → ℝ)
    (lam : ℝ) (W : Set V) : Prop :=
  ∀ X Y : Finset V, (X : Set V) ⊆ W → (Y : Set V) ⊆ W → Disjoint X Y →
    ∀ s : Edge H → ℝ, IsFractionalXYSeparator H X Y s →
      lam * min (weightOf μ X) (weightOf μ Y) ≤ ∑ e, s e

/-- p. 24. A pseudometric on `[k]` (identified with `Fin k`); distinct points may be at distance 0. -/
def IsPseudometric {k : ℕ} (d : Fin k → Fin k → ℝ) : Prop :=
  (∀ i j, 0 ≤ d i j) ∧ (∀ i, d i i = 0) ∧ (∀ i j, d i j = d j i) ∧
  ∀ i j l, d i j ≤ d i l + d l j

/-- p. 24. `d(A, B) = min_{i ∈ A, j ∈ B} d(i, j)` (used only for nonempty `A`, `B`). -/
noncomputable def setDist {k : ℕ} (d : Fin k → Fin k → ℝ) (A B : Finset (Fin k)) : ℝ :=
  sInf {c | ∃ i ∈ A, ∃ j ∈ B, c = d i j}

/-- The right-hand maximum of (10): `max_{∅ ≠ A, B ⊆ [k], A ∩ B = ∅} min{|A|, |B|} d(A, B)`
(a maximum over a finite set). -/
noncomputable def hubSeparation {k : ℕ} (d : Fin k → Fin k → ℝ) : ℝ :=
  sSup {c | ∃ A B : Finset (Fin k), A.Nonempty ∧ B.Nonempty ∧ Disjoint A B ∧
    c = ((min A.card B.card : ℕ) : ℝ) * setDist d A B}

/-- Inequality (10) of Lemma 6.4 with constant `C`: for every pseudometric `d` on `[k]` with
`k ≥ 2`, some `z` has `∑_u d(z, u) ≤ C · log₂ k · max … min{|A|,|B|} d(A, B)`. -/
def HubBound (C : ℝ) : Prop :=
  ∀ k : ℕ, 2 ≤ k → ∀ d : Fin k → Fin k → ℝ, IsPseudometric d →
    ∃ z : Fin k, ∑ u, d z u ≤ C * logTwo (k : ℝ) * hubSeparation d

end SparseIncidenceHom.WidthComparison.Supplement
Source
Matthias Lanzinger, STOC 2027 submission #662 (October 2026), p. 8 (Section 2.2: polymatroids, subw), p. 20 (touching sets, clique embeddings, equation (8)), p. 24 (vertex weightings, fractional (X,Y)-separators, (µ,λ)-connectivity, pseudometrics, d(A,B), inequality (10))

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me