lemmaroutine

Deterministic balanced incidence labeling

Lemma·lem:incidence-labels·§4.4 Choosing the variable and factor groups

Statement (paper)

Let (If)f∈F(I_f)_{f\in\mathcal F} satisfy , with n⩽M⩽bnn\le M\le bn, and put D=r2QD=r^{2Q} for integers r⩾2r\ge2 and Q⩾1Q\ge1. Suppose 2(b+w)D2⩽M,2Qr2⩽n. 2(b+w)D^2\le M,\qquad 2Qr^2\le n. One can deterministically choose av,df∈[r]Qa_v,d_f\in[r]^Q, with df(t)=1d_f(t)=1 for factors of empty scope, so that max⁡u∈B#{(f,v)∈A:(av,df)=u}⩽2MD,#{v∈[n]:av(t)=g}⩽2nr(t∈[Q], g∈[r]). \begin{aligned} \max_{u\in\mathcal B}\#\{(f,v)\in\mathcal A:(a_v,d_f)=u\} &\le\frac{2M}{D},\\ \#\{v\in[n]:a_v(t)=g\}&\le\frac{2n}{r} \qquad(t\in[Q],\ g\in[r]). \end{aligned} The construction takes poly⁡(n,M,∣F∣,D,Q,r,b,w)\poly(n,M,|\mathcal F|,D,Q,r,b,w) bit operations.

In plain English

Under n⩽M⩽bnn\le M\le bn, 2(b+w)D2⩽M2(b+w)D^2\le M and 2Qr2⩽n2Qr^2\le n with D=r2QD=r^{2Q}, one can deterministically assign labels av,df∈[r]Qa_v,d_f\in[r]^Q (with df(t)=1d_f(t)=1 for empty-scope factors) so that each label pair uu occurs on at most 2M/D2M/D incidences (f,v)(f,v), and each coordinate value g∈[r]g\in[r] at each coordinate t∈[Q]t\in[Q] is taken by at most 2n/r2n/r variables. This takes time polynomial in the parameters.

Why it's here

This is the balancing step that splits variables and factors into groups so that incidences spread nearly evenly across the DD label pairs and each variable coordinate stays evenly distributed. The proof shows random labels give small expected collision and imbalance potentials, then derandomizes by conditional expectations, computed exactly in polynomial time. Later layout and counting results use the resulting balanced groups.
Classified routine:
A standard probabilistic balancing argument: random labels have small expected collision and imbalance potentials, and the method of conditional expectations (Erdős–Selfridge / Spencer–Raghavan style derandomization) turns this into a deterministic labeling. Nothing beyond this bookkeeping appears to be new.

Uses

Nothing else in the paper

Used by

thmCounting zeros of sparse polynomials fasterlemLayout data is efficiently constructibleclaimNumerical checks with exhaustive fallback

Inside the proof

claimExpected collision and imbalance potentialsclaimConditional expectations yield balanced labelsclaimConditional expectations are efficiently computable

Sources

PaperOpen
Section
§4.4 Choosing the variable and factor groups
Page
—
Label
lem:incidence-labels
Line
main_full_version.tex:2442
Leannot aligned

Phase 2 aligns this node to a Lean declaration.