Lemma 8 — Pr[ℰ₃] ≤ 1/4 for every integer g > 2: G′ has at most (6β₂c²)^{g+1} cycles of length ≤ g
ProvedEDPHardness.IntegralityGap.lemma_8Let be the random hypergraph on vertices with independent hyperedges, each uniform among the -subsets, let be the graph on the hyperedges obtained from by shrinking every special edge, and let be the number of (simple) cycles of length at most in . The event (for the value ) is .
Let and assume . Then for every integer ,
Short cycles of are what a short non-canonical path must create together with a canonical path; the lemma says there are few of them.
Formalization Note The paper's definition says "cycles of length at most in ", but its proof ("a cycle of length in the graph ") and its use in Section 2.4 count cycles in ; cycles in are formalized. Each cycle is counted once, as its edge set. The proof needs no largeness of ; the hypotheses (the hyperedges exist) and (otherwise there are no hyperedges and the threshold can be negative) are the ones the statement needs to be the paper's.
import Mathlib import Definitions.Def_EDPHardness_IntegralityGap_GapInstance
namespace EDPHardness.IntegralityGap
theorem lemma_8 (n c : ℕ) (hc : 2 ≤ c) (hcn : c ≤ n) (hβ₂ : 0 < beta2 n c) (g : ℕ) (hg : 2 < g) :
hypProb n (numEdges n c) c (E3 n c g) ≤ 1 / 4 := by sorry
end EDPHardness.IntegralityGap
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.