Theorem 4.1 — Berge-acyclic -sparse instances
OpenSparseDisc.Supplement.theorem_4_1discrepancyhypergraphsp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-discrepancy
Let . If is a finite -sparse instance whose bundle hypergraph is Berge-acyclic, then
This is the instance-level theorem underlying Theorem 1.3 and retains declared supports that may strictly contain relevant coordinates.
Differences from the source:
- encoding: finite instance and bundle hypergraph → functions and items indexed by finite types, with declared support sparsity and acyclicity of the finite incidence graph; reason: Lean convention, preserving the paper's instance model
Preamble
import Mathlib import Definitions.Def_SparseDisc_IsInstance import Definitions.Def_SparseDisc_InstDiscLE import Definitions.Def_SparseDisc_Supplement_IsTSparseSupp import Definitions.Def_SparseDisc_Supplement_BergeAcyclic import Definitions.Def_SparseDisc_Supplement_K
Formal statement
namespace SparseDisc.Supplement
/-- **Theorem 4.1** (Zeng–Cao–Dai–Wang–Liao, *Sparse Discrepancy Beyond Additive Functions*, STOC
2027 submission manuscript (sha256 0f09ec60…25b81), p.19). Every Berge-acyclic `t`-sparse
instance has discrepancy at most `K t`.
**Formalization Note** Declared supports may strictly contain relevant coordinates. -/
theorem theorem_4_1 :
∀ (t : ℕ), 1 ≤ t → ∀ (V ι : Type) [Fintype V] [DecidableEq V]
[Fintype ι] [DecidableEq ι] (g : V → SparseDisc.Cube ι → ℝ)
(U : V → Finset ι), SparseDisc.IsInstance g U → IsTSparseSupp t U →
BergeAcyclic U → SparseDisc.InstDiscLE g (K t) := by sorry
end SparseDisc.Supplement
Source
Zeng–Cao–Dai–Wang–Liao, Sparse Discrepancy Beyond Additive Functions, STOC 2027 submission (manuscript sha256 0f09ec60…), Theorem 4.1, p.19