Proposition 6.5 — heavy, connected terminal cliques force large clique embedding power
OpenSparseIncidenceHom.WidthComparison.Supplement.proposition_6_5clique-embeddingsconnectivityhypergraphsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a constant satisfying inequality (10) of Lemma 6.4 for every and every pseudometric on . Let be a finite hypergraph, a nonnegative vertex weighting of , and disjoint cliques of the primal graph with . Suppose their union is -connected for some , and for every . Then
Combined with Lemma 6.3 this shows that unbounded submodular width forces unbounded clique embedding power (Lemma 6.2).
Formalization Note is to base two. The constant of Lemma 6.4 enters only through inequality (10), so the statement is made for every positive constant satisfying (10).
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
- reading: C_H, the constant of Lemma 6.4 → any C_H > 0 satisfying inequality (10); reason: the source refers to "the" constant of Lemma 6.4, which is any constant for which (10) holds; the proof uses only (10)
Preamble
import Mathlib import Definitions.Def_SparseIncidenceHom_WidthComparison_Supplement_Widths
Formal statement
namespace SparseIncidenceHom.WidthComparison.Supplement
open SparseIncidenceHom.WidthComparison
/-- Lanzinger, STOC 2027 submission #662, Proposition 6.5, p. 26 (inequality (12)). `C_H` is any
positive constant for which inequality (10) of Lemma 6.4 holds. -/
theorem proposition_6_5 (C_H : ℝ) (hC : 0 < C_H) (hhub : HubBound C_H)
(V : Type) [Fintype V] (H : FiniteHypergraph V) (μ : V → ℝ) (hμ : ∀ v, 0 ≤ μ v)
(k : ℕ) (hk : 8 ≤ k) (K : Fin k → Finset V)
(hclique : ∀ i, (primal H).IsClique (K i : Set V))
(hdisj : ∀ i j, i ≠ j → Disjoint (K i) (K j))
(lam : ℝ) (hlam : 0 < lam) (hconn : IsMuLambdaConnected H μ lam (⋃ i, (K i : Set V)))
(hmass : ∀ i, (1 : ℝ) / 2 ≤ weightOf μ (K i)) :
lam * Real.sqrt (k : ℝ) / (8 * C_H * logTwo (k : ℝ)) ≤ cliqueEmbeddingPower H := by sorry
end SparseIncidenceHom.WidthComparison.Supplement
Source
Matthias Lanzinger, STOC 2027 submission #662 (October 2026), p. 26, Proposition 6.5 (inequality (12)); proof pp. 26–27