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 (1992) 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 a lemma due to Beck and Spencer (1983) which, in turn, was based on the floating variable method introduced by Beck and Fiala (1981) 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 (2003).