Concept icon
Concept

Bounding edge-label collisions by their average squared imbalance

Independently give each vertex a uniform label in [r]^a. Let X_gamma count wires with one particular ordered pair of endpoint labels, and let D_arr=r^(2a). Use the potential sum_gamma (X_gamma-M/D_arr)^2. Its expectation, meaning its average over all labelings, is at most 2M Delta. Expanding it sums, over ordered pairs of wires, their probability of equal label pairs minus 1/D_arr. Disjoint-endpoint pairs contribute zero. At most 2M Delta ordered pairs share an endpoint, including a wire paired with itself, and each contributes at most one. Parallel wires must be counted as distinct wires.

0

1

Concept icon
Updated 2026-11-08

Contributors are:

Who are from:

Tags

Math