claimroutineinferred_dep

Conditional expectations yield balanced labels

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

Statement (paper)

One can fix the

a_v

and the

d_f

for nonempty

I_f

one at a time, deterministically, so that the final value of

\frac{\Phi}{M(b+w)}+\frac{\Xi}{Qn}

is at most two. Consequently

c_u\le\frac MD+\sqrt{2M(b+w)}

for every

u\in\mathcal B

and

n_{t,g}\le\frac nr+\sqrt{2Qn}

for all

t\in[Q]

g\in[r]

, and under these give

c_u\le 2M/D

and

n_{t,g}\le 2n/r

In plain English

The labels

a_v

and

d_f

(nonempty

I_f

) can be fixed one at a time deterministically so that

\frac{\Phi}{M(b+w)}+\frac{\Xi}{Qn}\le 2

. This gives

c_u\le M/D+\sqrt{2M(b+w)}

and

n_{t,g}\le n/r+\sqrt{2Qn}

, which under the hypotheses become

c_u\le 2M/D

and

n_{t,g}\le 2n/r

Why it's here

By the previous claim the random labeling has expected value of the combined potential at most 2, so the method of conditional expectations, choosing each label to not increase the conditional expectation, yields a fixed labeling with value at most 2. Since each potential is a sum of squared deviations, it bounds every single deviation by a square root, and the size hypotheses

2(b+w)D^2\le M

and

2Qr^2\le n

make the square-root terms at most

M/D

and

n/r

, giving the two stated balance bounds of the lemma.

Classified routine:

Standard method of conditional expectations (derandomization, Erdős–Selfridge / Raghavan–Spencer) applied to the expected potential bound from the previous claim, followed by a bound on each squared deviation and arithmetic using the size hypotheses.

Uses

claimExpected collision and imbalance potentials

Used by

claimConditional expectations are efficiently computable

Sources

PaperOpen

Section: §4.4 Choosing the variable and factor groups
Page: —
Label: —
Line: main_full_version.tex:2496

Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

info
inferred_dep
outline: "Conditional expectations yield balanced labels" rests on claim-lem-incidence-labels-1