Concept
Choosing a balanced labeling by exact conditional averages
Fix vertex labels one at a time. The average of the remaining conditional averages, over all possible labels for the next vertex, equals the current average. At least one choice is therefore no larger; choose a minimizing label. Starting from the collision bound yields a final potential at most 2M Delta without random sampling. Each candidate average can be computed by enumerating ordered wire pairs: their probabilities involve at most four vertices. The label alphabet r^a is polynomial in s under the parameter bounds, so enumerating those few labels per pair is polynomial work. There is no need to enumerate all complete vertex labelings.
0
1
Updated 2026-11-08
Tags
Math