lemmaroutineinferred_dep

Rare sets carry little edge mass

Lemma·inc:rare·§2.4 Matching labels and uniformly rare sets

Statement (paper)

Let δt→0\delta_t\to0 be any nonnegative sequence. The estimates below hold uniformly over all indicated subsets, with error factors depending only on δt,ξt\delta_t,\xi_t and the fixed constants in : \begin{enumerate}[label=\textup{(\roman*)}] \item If F⊆PF\subseteq P, G⊆QG\subseteq Q, and h=μ(F)≤δth=\mu(F)\le\delta_t, while k=κ(G)k=\kappa(G) is arbitrary, then PE(F,G)≤C(δtη+ξt)hk=o(1)hk. \Prob_E(F,G)\le C(\delta_t^\eta+\xi_t)\sqrt{hk} =o(1)\sqrt{hk}. The same assertion holds with the sides interchanged. \item If also k≤δtk\le\delta_t, then PE(F,G)≤C2(δt2η+ξt)(h+k)=o(1)(h+k). \Prob_E(F,G)\le\tfrac C2(\delta_t^{2\eta}+\xi_t)(h+k) =o(1)(h+k). \item If F⊆PF\subseteq P and h=μ(F)≤δth=\mu(F)\le\delta_t, then under the wedge law, P(p∈F,r∈F)=o(1)h. \Prob(p\in F,r\in F)=o(1)h. \end{enumerate} In particular, the error factors may be taken outside sums or integrals over any family of sets whose marginal masses obey the same uniform bound δt\delta_t.

In plain English

If F⊆PF\subseteq P has marginal mass h=μ(F)≤δth=\mu(F)\le\delta_t, then for any G⊆QG\subseteq Q with k=κ(G)k=\kappa(G), PE(F,G)≤C(δtη+ξt)hk=o(1)hk\Prob_E(F,G)\le C(\delta_t^\eta+\xi_t)\sqrt{hk}=o(1)\sqrt{hk}, and likewise with the sides swapped. If both h,k≤δth,k\le\delta_t then PE(F,G)=o(1)(h+k)\Prob_E(F,G)=o(1)(h+k), and under the wedge law P(p∈F,r∈F)=o(1)h\Prob(p\in F,r\in F)=o(1)h; all error factors are uniform over the sets.

Why it's here

This turns the expansion bound of the incidence piece into a rare-event statement: when one or both sets have vanishing marginal mass, their joint edge mass is a vanishing fraction of the natural scale. Part (ii) follows from (i) by AM-GM on hk\sqrt{hk}, and the uniform error factors let later arguments pull the o(1)o(1) outside sums over families of rare sets, such as the exception sets of the later moment bounds.
Classified routine:
Direct consequence of the expansion bound in the incidence piece (inc-piece), obtained by plugging in the small marginal mass; part (ii) follows by AM-GM on sqrt(hk) and part (iii) by the same estimate under the wedge law.

Uses

propIncidence piece with degree and expansion control

Used by

lemRare exceptions: comparison, first moments, joint bounds

Sources

PaperOpen
Section
§2.4 Matching labels and uniformly rare sets
Page
—
Label
inc:rare
Line
sections/01-incidence.tex:424
Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    critique: Lemma inc:rare's proof (01-incidence.tex:454-473) follows from , derived from Proposition inc:piece.