Lemma 7.4 — Random boundary expanders for graph PHP
ProvedSemAC02.Supplement.lemma_7_4_php_boundary_expanderspigeonhole-principlepolynomial-calculusproof-complexityrandom-graphs
Let and . For all sufficiently large , sample a bipartite graph with pigeons and holes by including each possible edge independently with probability . The probability that the graph is an -boundary expander, every pigeon has degree at most , and every hole has degree at most tends to one as .
The finite weighted sum in the formal statement is precisely this product distribution on the edge indicators. The conclusions are the existing predicate Lemma74Concl. As in the source, the random model is used only for sufficiently large , when ; values at finitely many smaller do not affect the limit. No hypotheses or conclusions of Lemma 7.4 are changed.
Preamble
import Mathlib import Definitions.Def_SemAC02_Supplement_phpG open Filter Topology attribute [local instance] Classical.propDecidable
Formal statement
namespace SemAC02.Supplement
theorem lemma_7_4_php_boundary_expanders :
Tendsto (fun n : ℕ =>
∑ x : (Fin n × Fin (2*n) → Bool),
if Lemma74Concl ({Adj := fun u v => x (v,u)=true} : PCNonBool.BipGraph (Fin (2*n)) (Fin n))
then ∏ e : Fin n × Fin (2*n),
(if x e then (php74Delta n : ℝ)/n else 1-(php74Delta n : ℝ)/n)
else 0) atTop (𝓝 1) := by sorry
end SemAC02.SupplementSource
Alekseev, Gryaznov, Itsykson, Pitassi, Robere, Tzameret, Hard Instances for Strong Semantic Proof Systems, https://www.doc.ic.ac.uk/~itzamere/Reslin_Simplification.pdf, Lemma 7.4, printed p.52 (PDF p.54), and Appendix D, printed p.73 (PDF p.75).