Alon's transmitting problem and multicolor Beck--Spencer Lemma

The Hamming graph $H(n,q)$ is defined on the vertex set \1,2,…,q\ⁿ and two vertices are adjacent if and only if they differ in precisely one coordinate. Alon proved that for any sequence v₁,…,vb of b= n2 vertices of $H(n,2)$, there is a vertex whose distance from vᵢ is at least $b-i+1$ for all 1≤ i≤ b. In this note, we prove that for any q≥ 3 and any sequence v₁,…,vb of b=(1-1q)n vertices of $H(n,q)$, there is a vertex whose distance from vᵢ is at least $b-i+1$ for all 1≤ i≤ b. Alon used the Beck--Spencer Lemma which, in turn, was based on the floating variable method introduced by Beck and Fiala who studied combinatorial discrepancies. For our proof, we extend the Beck--Spencer Lemma by using a multicolor version of the floating variable method due to Doerr and Srivastav.