Lemma 6.3 — high submodular width yields many heavy, highly connected primal cliques
OpenSparseIncidenceHom.WidthComparison.Supplement.lemma_6_3connectivityhypergraphsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1submodular-width
There are absolute constants such that every finite hypergraph with admits a nonnegative vertex weighting and disjoint nonempty cliques of the primal graph such that
and is -connected.
The constants are fixed before the hypergraph. This is the consequence of Marx's results that starts the passage from submodular width to clique embeddings.
Formalization Note ; -connectivity uses fractional -separators of hyperedges, as in the definition item SparseIncidenceHom.WidthComparison.Supplement.Widths. The weighting is only required to be nonnegative, as printed.
Differences from the source:
- generalization: the hypergraph H is nonempty and connected (p. 7 standing convention) → H is any finite hypergraph (published FiniteHypergraph), possibly empty or disconnected; reason: on nonempty connected H the Lean statement is the source's
Preamble
import Mathlib import Definitions.Def_SparseIncidenceHom_WidthComparison_Supplement_Widths
Formal statement
namespace SparseIncidenceHom.WidthComparison.Supplement
open SparseIncidenceHom.WidthComparison
/-- Lanzinger, STOC 2027 submission #662, Lemma 6.3, p. 24. The constants precede every
hypergraph. Cliques are cliques of the primal graph `P(H)`. -/
theorem lemma_6_3 :
∃ β cT w₀ : ℝ, 0 < β ∧ 0 < cT ∧ 0 < w₀ ∧
∀ (V : Type) [Fintype V] (H : FiniteHypergraph V), w₀ ≤ submodularWidth H →
∃ μ : V → ℝ, (∀ v, 0 ≤ μ v) ∧
∃ (k : ℕ) (K : Fin k → Finset V),
(∀ i, (K i).Nonempty) ∧ (∀ i, (primal H).IsClique (K i : Set V)) ∧
(∀ i j, i ≠ j → Disjoint (K i) (K j)) ∧
cT * Real.sqrt (submodularWidth H) ≤ (k : ℝ) ∧
(∀ i, (1 : ℝ) / 2 ≤ weightOf μ (K i)) ∧
IsMuLambdaConnected H μ β (⋃ i, (K i : Set V)) := by sorry
end SparseIncidenceHom.WidthComparison.Supplement
Source
Matthias Lanzinger, STOC 2027 submission #662 (October 2026), p. 24, Lemma 6.3 (consequence of [Mar13, Theorem 5.1 and Lemma 6.5]); proof p. 24