Theorem 3.4 — exact observation threshold
OpenHypRecov.Supplement.theorem_3_4hypergraphslinear-sketchingp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-recoverystreaming-algorithms
Let , , and . Among orders , the least order whose complete multiplicity-preserving -observation determines for every simple unweighted -uniform hypergraph on the fixed vertex set is
Thus this order is sufficient for every input, while every smaller order admits two inputs with the same observation and different -crisp edge families.
Differences from the source:
- encoding: on a fixed -vertex set →
HypRecov.qid r kand anIsLeastpredicate over simple uniform hypergraphs onFin n; reason: the displayed formula is independent of , whileFin nfixes the common labelled vertex set andIsLeastretains both directions
Preamble
import Mathlib import Definitions.Def_HypRecov_qid import Definitions.Def_HypRecov_Supplement_IsCutDegenerate set_option autoImplicit false
Formal statement
namespace HypRecov.Supplement
/-- **Theorem 3.4 (Exact observation threshold).** Zhang, Chen, Shen, *Hypergraph Recovery from
Anonymous Projection Streams*, STOC 2027 submission (manuscript sha256 719dcfff…), Theorem 3.4,
p.7 (PDF p.8). For `n ≥ 2r`, `r ≥ 2`, and `k ≥ 2`, the least multiplicity-preserving
projection order that determines the complete family of `k`-crisp edges of every simple unweighted
`r`-uniform hypergraph on `Fin n` is `min r (1 + ceil(log₂ k))`.
**Formalization Note.** `IsLeast` records both directions: `qid r k` determines `B_k(H)`, and every
smaller order in `{1,…,r}` fails for some pair of simple `r`-uniform hypergraphs on the same fixed
vertex set. -/
theorem theorem_3_4 (n r k : ℕ) (hn : 2 * r ≤ n) (hr : 2 ≤ r) (hk : 2 ≤ k) :
IsLeast {q : ℕ | 1 ≤ q ∧ q ≤ r ∧ DeterminesCrisp n r k q} (HypRecov.qid r k)
:= by sorry
end HypRecov.Supplement
Source
Zhang, Chen, Shen, Hypergraph Recovery from Anonymous Projection Streams, STOC 2027 submission (manuscript sha256 719dcfff4dc2eba2d8c5a3c51679a08cfb11f076546dea963c6376a2b9da2c82), Theorem 3.4, p.7 (PDF p.8)