Documentation

Atlas.ProbabilisticMethodsInCombinatorics.code.Chapter6.LopsidedLLLSymmetric

theorem LopsidedLLL.exp_neg_inv_le_real (m : ) (hm : 0 < m) :
Real.exp (-(1 / m)) m / (m + 1)

Real-valued helper: for $m \ge 1$ one has $e^{-1/m} \le m/(m+1)$.

theorem LopsidedLLL.one_sub_inv_pow_ge_inv_exp_real (d : ) :
Real.exp (-1) (1 - 1 / (d + 1)) ^ d

Real-valued inequality $e^{-1} \le (1 - 1/(d+1))^d$, used in the symmetric Lopsided LLL.

ℝ≥0∞-valued version of one_sub_inv_pow_ge_inv_exp_real: $e^{-1} \le (1 - (d+1)^{-1})^d$ as extended nonnegative reals.

theorem LopsidedLLL.lopsided_local_lemma_symmetric {Ω : Type u_1} [MeasurableSpace Ω] {μ : MeasureTheory.Measure Ω} [MeasureTheory.IsProbabilityMeasure μ] {n : } (A : Fin nSet Ω) (hA : ∀ (i : Fin n), MeasurableSet (A i)) (N : Fin nFinset (Fin n)) (hlop : ∀ (i : Fin n), SFinset.univ \ (N i {i}), μ[A i | avoidSet A S] μ (A i)) (d : ) (p : ENNReal) (hNd : ∀ (i : Fin n), (N i).card d) (hprob : ∀ (i : Fin n), μ (A i) p) (hepd : ENNReal.ofReal (Real.exp 1) * p * (d + 1) 1) :
0 < μ (⋂ (i : Fin n), (A i))

Symmetric Lopsided Local Lemma (Corollary 6.5.2): if every $\mu(A_i) \le p$, every lopsidependency neighbourhood satisfies $|N(i)| \le d$, and $e \cdot p \cdot (d+1) \le 1$, then $\mu(\bigcap_i \overline{A_i}) > 0$.