Proposition 11:
ProvedFranklKupavskii2022.EMC.indicator_covariance_boundconcentration-inequalitieskneser-graphsp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be integers with , let , , and let be a uniformly random -matching of -sets in . With , for any in
The bound comes from the spectrum of the Kneser graph and gives , the Chebyshev-type concentration of Lemma 10.
Preamble
import Mathlib import Definitions.Def_FranklKupavskii2022_EMC_tMatchings
Formal statement
namespace FranklKupavskii2022.EMC
/-- Proposition 11 (Frankl–Kupavskii, arXiv:1806.08855v3, p. 6): in the setting of Lemma 10
(`m ≥ tl`, `G ⊂ \binom{[m]}{l}`, `α := |G|/\binom{m}{l}`, `B` a uniformly random `t`-matching of
`l`-sets, `η_i` the indicator that the `i`-th set of `B` lies in `G`), for any `i, j ∈ [t]` with
`i ≠ j` we have `|Cov[η_i, η_j]| ≤ \frac{α(1−α)}{t−1}`.
**Formalization Note.** Positions are `Fin t`; `i ≠ j` forces `t ≥ 2`, so `t − 1 > 0` in `ℝ`. The
covariance is taken under the uniform distribution on `tMatchings m l t` (ordered `t`-tuples of
pairwise disjoint `l`-subsets of `[m]`), which is nonempty because `t * l ≤ m`. -/
theorem indicator_covariance_bound (m l t : ℕ) (hm : t * l ≤ m) (G : Finset (Finset ℕ))
(hG : G ⊆ (Finset.Icc 1 m).powersetCard l) (i j : Fin t) (hij : i ≠ j) :
|cov m l t (etaI G i) (etaI G j)| ≤
density m l G * (1 - density m l G) / ((t : ℝ) - 1) := by sorry
end FranklKupavskii2022.EMC
Source
Frankl–Kupavskii, The Erdős Matching Conjecture and concentration inequalities, arXiv:1806.08855v3, Proposition 11, p. 6 (setting of Lemma 10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.