claimroutine

Expected collision and imbalance potentials

Claim·§4.4 Choosing the variable and factor groups·inside lemDeterministic balanced incidence labeling

Statement (paper)

With all ava_v and all dfd_f for nonempty IfI_f independent and uniform on [r]Q[r]^Q, and dfd_f identically one for empty IfI_f, the potentials Φ=∑u∈B(cu−M/D)2\Phi=\sum_{u\in\mathcal B}(c_u-M/D)^2 and Ξ=∑t=1Q∑g=1r(nt,g−n/r)2\Xi=\sum_{t=1}^Q\sum_{g=1}^r(n_{t,g}-n/r)^2, where nt,g=#{v:av(t)=g}n_{t,g}=\#\{v:a_v(t)=g\}, satisfy EΦ⩽M(b+w)\mathbb E\Phi\le M(b+w) and EΞ=Qn(1−1/r)⩽Qn\mathbb E\Xi=Qn(1-1/r)\le Qn.

In plain English

If all ava_v and the dfd_f for nonempty IfI_f are chosen independently and uniformly from [r]Q[r]^Q, with dfd_f fixed to one for empty IfI_f, then the label-collision potential Φ=∑u∈B(cu−M/D)2\Phi=\sum_{u\in\mathcal B}(c_u-M/D)^2 has EΦ⩽M(b+w)\mathbb E\Phi\le M(b+w). The coordinate-imbalance potential Ξ=∑t,g(nt,g−n/r)2\Xi=\sum_{t,g}(n_{t,g}-n/r)^2 has EΞ=Qn(1−1/r)⩽Qn\mathbb E\Xi=Qn(1-1/r)\le Qn.

Why it's here

This bounds the expected size of two variance-like potentials under random labels. The next claim can then derandomize by conditional expectations to get a labeling where both potentials are small, which gives the stated bounds on label-pair counts and on per-coordinate group sizes.
Classified routine:
A direct second-moment (variance) calculation for sums of indicator variables under uniform independent random labels. It is the standard first step before derandomizing by the method of conditional expectations.

Uses

Nothing else in the paper

Used by

claimConditional expectations yield balanced labels

Sources

PaperOpen
Section
§4.4 Choosing the variable and factor groups
Page
—
Label
—
Line
main_full_version.tex:2463
Leannot aligned

Phase 2 aligns this node to a Lean declaration.