claimroutineinferred_dep

Copy normalization to unit incident weight

Copy normalization gives unit incident weight with NO value ≤ 2γ02\gamma_0
equalizes left weights before rounding
Claim·§A.1 A simple strong-left form of Unique Games·inside lemUnique Games with constant left degree and strong satisfaction

Statement (paper)

Let X1X_1 be the set of copies, where each xx with wx>0w_x>0 has nx=⌊2∣X0∣wx⌋n_x=\lfloor 2|X_0|w_x\rfloor copies carrying local edge weights wxy/wxw_{xy}/w_x. Then ∣X0∣≤∣X1∣=∑xnx≤2∣X0∣|X_0|\le |X_1|=\sum_x n_x\le 2|X_0| and the incident weight at each copy is one. On a NO input the copy game's normalized value is at most 2γ02\gamma_0. On a YES input there is a labeling of the copy game in which more than a 1−u1-u fraction of X1X_1 has local satisfied weight at least 1−u1-u.

In plain English

Replace each left vertex xx of positive weight wxw_x by nx=⌊2∣X0∣wx⌋n_x=\lfloor 2|X_0|w_x\rfloor copies with local edge weights wxy/wxw_{xy}/w_x. The resulting copy set X1X_1 satisfies ∣X0∣≤∣X1∣≤2∣X0∣|X_0|\le|X_1|\le 2|X_0|, each copy has incident weight one, the NO-case normalized value is at most 2γ02\gamma_0, and in the YES case a labeling exists where more than a 1−u1-u fraction of copies have local satisfied weight at least 1−u1-u.

Why it's here

This turns the weighted game into one where every left vertex has the same total weight, which is needed before the weights can be rounded into an unweighted multigraph in the next claim. Flooring with the factor 2∣X0∣2|X_0| loses at most a constant factor in size and soundness, giving 2γ02\gamma_0, which the parameter inequalities from the earlier claim absorb. In the YES case, the Unique Games Theorem's completeness is converted into a high fraction of copies that are almost fully satisfied, using the constants uu and ζ0\zeta_0.
Classified routine:
Standard vertex-duplication/weight-normalization bookkeeping (as in regularization reductions for Unique Games, e.g. Khot–Regev style left-regularization), combined with a Markov-type averaging of the UG theorem's completeness guarantee.

Uses

claimParameters fixed before invoking UG theoremthmThe Unique Games Theorem

Used by

claimRounding weights into unweighted multigraph

Sources

PaperOpen
Section
§A.1 A simple strong-left form of Unique Games
Page
—
Label
—
Line
appendices/finite-consequences.tex:69
Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    outline: "Copy normalization to unit incident weight" rests on claim-lem-simple-strong-left-1
  • info
    inferred_dep
    outline: "Copy normalization to unit incident weight" rests on thm:ugc