Finite unmarked and marked hypergraph experiments
DefinitionExpandingCodes_PolynomialStretch_Supplement_HypergraphsA simple -uniform hypergraph on is its indicator vector on the set of unordered -element subsets. The published uniform-hypergraph object and its product Bernoulli law are reused. Edges are listed lexicographically by increasing endpoint lists. The incidence matrix has one row per present edge in that order. Its column count retains all vertices, including isolated vertices.
For a fixed hypergraph on , let have independent Bernoulli- edge indicators and independently choose a uniform injection . The planted experiment is
An edge already present is included once. Expectations are finite sums of singleton probabilities; uniform averages divide by the cardinality of the finite sample space. The empty injection family is assigned average zero only outside the domain used in the results.
A marked edge is a pair with , and . Marked background indicators are mutually independent, including different marks on the same support. The marked planting experiment transports both sets. Marked incidence rows ignore the mark when counting vertices, but retain one row for each marked edge. The XOR-MAJ bit is the parity on added modulo two to the strict majority on .
For an edge family , its spanned vertices are . The expansion predicate for the non-asymptotic result is
These objects supply the actual random experiments and expansion hypotheses in the supplement.
import Mathlib
import Definitions.Def_RandomIsetThreshold_Degree_Hypergraph
import Definitions.Def_ExpandingCodes_PolynomialStretch_BinaryModel
set_option autoImplicit false
open scoped BigOperators Classical
namespace ExpandingCodes.PolynomialStretch.Supplement
noncomputable section
abbrev Edge := RandomIsetThreshold.Degree.Edge
abbrev Hypergraph := RandomIsetThreshold.Degree.Cube
/-- The finite expectation, avoiding any integrability convention. -/
def finiteMean {α : Type} [Fintype α] [MeasurableSpace α] (μ : MeasureTheory.Measure α) (f : α → ℝ) : ℝ :=
∑ x, μ.real {x} * f x
def uniformMean {α : Type} [Fintype α] (f : α → ℝ) : ℝ :=
(∑ x, f x) / Fintype.card α
def finiteProb {α : Type} [Fintype α] [MeasurableSpace α] (μ : MeasureTheory.Measure α) (E : α → Prop) : ℝ :=
finiteMean μ (fun x => if E x then 1 else 0)
abbrev nullLaw (N k : ℕ) (p : unitInterval) :=
RandomIsetThreshold.Degree.graphLaw N k p
/-- Lexicographic order on increasing lists of endpoints. -/
def edgeOrder {N k : ℕ} (e f : Edge N k) : Bool :=
decide (List.Lex (· < ·) (e.val.sort (· ≤ ·)) (f.val.sort (· ≤ ·)) ∨ e = f)
def allEdges (N k : ℕ) : List (Edge N k) :=
(Finset.univ : Finset (Edge N k)).toList.mergeSort edgeOrder
def presentEdges {N k : ℕ} (G : Hypergraph N k) : List (Edge N k) :=
(allEdges N k).filter G
def edgeCount {N k : ℕ} (G : Hypergraph N k) : ℕ := (presentEdges G).length
def incidence {N k : ℕ} (G : Hypergraph N k) : Generator (edgeCount G) N :=
fun i v => if v ∈ ((presentEdges G).get i).val then 1 else 0
def edgeBits {N k : ℕ} (G : Hypergraph N k) : List Bool := (allEdges N k).map G
def edgeImage {n N k : ℕ} (π : Fin n ↪ Fin N) (e : Edge n k) : Edge N k :=
⟨e.val.map π, by simp [e.property]⟩
def plant {n N k : ℕ} (H : Hypergraph n k) (G : Hypergraph N k)
(π : Fin n ↪ Fin N) : Hypergraph N k :=
fun e => G e || decide (∃ f : Edge n k, H f = true ∧ edgeImage π f = e)
/-- Independent background and a uniform injection of ALL n vertices, including isolated ones.
The empty injection family has uniformMean=0 outside N≥n; no theorem uses that case. -/
def plantedMean {n N k : ℕ} (H : Hypergraph n k) (p : unitInterval)
(f : Hypergraph N k → ℝ) : ℝ :=
finiteMean (nullLaw N k p) fun G =>
uniformMean fun π : Fin n ↪ Fin N => f (plant H G π)
def edgesFinset {N k : ℕ} (G : Hypergraph N k) : Finset (Edge N k) :=
Finset.univ.filter fun e => G e = true
def spannedVertices {N k : ℕ} (F : Finset (Edge N k)) : Finset (Fin N) :=
F.biUnion fun e => e.val
/-- Exact finite expansion condition used in Theorem 5.1. -/
def PatternExpansion {n k : ℕ} (H : Hypergraph n k) (D : ℕ) (γ : ℝ) : Prop :=
∀ F ⊆ edgesFinset H, F.card ≤ D →
γ * k * F.card ≤ ((spannedVertices F).card : ℝ)
/-- Marked edges form their own independent-coordinate background, not a consequence of
unmarked planting. A mark is an unordered parity half. -/
abbrev MarkedEdge (N ℓ : ℕ) :=
{z : Edge N (2 * ℓ) × Finset (Fin N) // z.2 ⊆ z.1.val ∧ z.2.card = ℓ}
abbrev MarkedGraph (N ℓ : ℕ) := MarkedEdge N ℓ → Bool
def markedOrder {N ℓ : ℕ} (e f : MarkedEdge N ℓ) : Bool :=
edgeOrder e.val.1 f.val.1 && decide (e.val.1 ≠ f.val.1) ||
decide (e.val.1 = f.val.1 ∧
(List.Lex (· < ·) (e.val.2.sort (· ≤ ·)) (f.val.2.sort (· ≤ ·)) ∨ e = f))
def allMarkedEdges (N ℓ : ℕ) : List (MarkedEdge N ℓ) :=
(Finset.univ : Finset (MarkedEdge N ℓ)).toList.mergeSort markedOrder
def markedList {N ℓ : ℕ} (G : MarkedGraph N ℓ) : List (MarkedEdge N ℓ) :=
(allMarkedEdges N ℓ).filter G
def markedBits {N ℓ : ℕ} (G : MarkedGraph N ℓ) : List Bool := (allMarkedEdges N ℓ).map G
def markedIncidence {N ℓ : ℕ} (G : MarkedGraph N ℓ) :
Generator (markedList G).length N :=
fun i v => if v ∈ ((markedList G).get i).val.1.val then 1 else 0
def markedNullLaw (N ℓ : ℕ) (p : unitInterval) : MeasureTheory.Measure (MarkedGraph N ℓ) :=
MeasureTheory.Measure.pi fun _ => ProbabilityTheory.bernoulliMeasure true false p
def markedImage {n N ℓ : ℕ} (π : Fin n ↪ Fin N) (e : MarkedEdge n ℓ) : MarkedEdge N ℓ :=
⟨(edgeImage π e.val.1, e.val.2.map π), by
constructor
· exact Finset.map_subset_map.mpr e.property.1
· simpa using e.property.2⟩
def markedPlant {n N ℓ : ℕ} (H : MarkedGraph n ℓ) (G : MarkedGraph N ℓ)
(π : Fin n ↪ Fin N) : MarkedGraph N ℓ :=
fun e => G e || decide (∃ f : MarkedEdge n ℓ, H f = true ∧ markedImage π f = e)
def markedPlantedMean {n N ℓ : ℕ} (H : MarkedGraph n ℓ) (p : unitInterval)
(f : MarkedGraph N ℓ → ℝ) : ℝ :=
finiteMean (markedNullLaw N ℓ p) fun G =>
uniformMean fun π : Fin n ↪ Fin N => f (markedPlant H G π)
/-- XOR of the parity half with strict majority of the other half (ℓ is odd in §3.4). -/
def xorMaj {N ℓ : ℕ} (e : MarkedEdge N ℓ) (x : Fin N → Bool) : Bool :=
xor (decide ((∑ v ∈ e.val.2, if x v then 1 else 0 : ℕ) % 2 = 1))
(decide (ℓ < 2 * ((e.val.1.val \ e.val.2).filter fun v => x v).card))
end
end ExpandingCodes.PolynomialStretch.Supplement