Bundle hyperedges
DefinitionSparseDisc_Supplement_bundleEdgeshypergraphsp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-discrepancy
For declared supports , a set of at least two functions is a bundle hyperedge when some item has reader set exactly . Private singleton bundles are not hyperedges.
Definition code
import Mathlib
namespace SparseDisc.Supplement
open Classical in
/-- The non-private hyperedges of the bundle hypergraph: a set `S` of at least two functions is an
edge exactly when some item has declared reader set exactly `S` (Zeng–Cao–Dai–Wang–Liao,
*Sparse Discrepancy Beyond Additive Functions*, STOC 2027 submission manuscript (sha256
0f09ec60…25b81), Definition 2.3, p.12). -/
noncomputable def bundleEdges {V ι : Type} [Fintype V] [DecidableEq V] [Fintype ι]
(U : V → Finset ι) : Finset (Finset V) :=
(Finset.univ : Finset (Finset V)).filter (fun S =>
2 ≤ S.card ∧ ∃ j : ι, Finset.univ.filter (fun v => j ∈ U v) = S)
end SparseDisc.Supplement
Source
Zeng–Cao–Dai–Wang–Liao, Sparse Discrepancy Beyond Additive Functions, STOC 2027 submission (manuscript sha256 0f09ec60…), Definition 2.3, p.12