claimroutineinferred_dep

Rounding weights into unweighted multigraph

Rounding weights gives an unweighted multigraph with left degree

L_2|Y|

gives the constant left degree

Claim·§A.1 A simple strong-left form of Unique Games·inside lemUnique Games with constant left degree and strong satisfaction

Statement (paper)

Let

\alpha=L_2|Y|

. One can construct from the weighted copy game an unweighted multigraph

\Phi_{\mathrm{occ}}

of left degree

\alpha

, in which every occurrence at a pair retains that pair's permutation, such that on a NO input

\val(\Phi_{\mathrm{occ}})\le 2\gamma_0+\frac1{L_2}<\beta\gamma

, and on a YES input the labeling lifted from

\Phi_0

has satisfied occurrence fraction at least

1-a

, where

a=u+1/L_2

, at more than a

1-u

fraction of

X_1

In plain English

From the weighted copy game one builds an unweighted multigraph

\Phi_{\mathrm{occ}}

with left degree

\alpha=L_2|Y|

, where each occurrence keeps its pair's permutation. On NO inputs

\val(\Phi_{\mathrm{occ}})\le 2\gamma_0+1/L_2<\beta\gamma

, and on YES inputs the lifted labeling has satisfied occurrence fraction at least

1-a

with

a=u+1/L_2

on more than a

1-u

fraction of

X_1

Why it's here

This step removes the edge weights by turning the unit incident weight of each copy in

X_1

into a fixed number

\alpha

of unweighted edge occurrences, which gives the constant left degree needed later. Rounding to multiples of

1/L_2

costs only

1/L_2

in both soundness and completeness, so the bounds

2\gamma_0

and

1-u

from copy normalization carry over with that small loss. The resulting multigraph is the input for the tagging step and the distinct-tag simple-graph step that follow.

Classified routine:

A standard weight-rounding step: each copy's normalized incident weights are rounded to multiples of 1/L_2 and replaced by parallel edge occurrences. This is the usual trick for removing weights in CSP reductions, here applied directly to the copy-normalized game from the previous claim, with an additive 1/L_2 loss.

Uses

claimCopy normalization to unit incident weight

Used by

claimTagged right copies preserve valueclaimDistinct-tag graph strongly satisfied on YES

Sources

PaperOpen

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

Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

info
inferred_dep
outline: "Rounding weights into unweighted multigraph" rests on claim-lem-simple-strong-left-2