Alon's transmitting problem and multicolor Beck--Spencer Lemma
<|reference_start|>Alon's transmitting problem and multicolor Beck--Spencer Lemma: The Hamming graph $H(n,q)$ is defined on the vertex set $\{1,2,\ldots,q\}^n$ and two vertices are adjacent if and only if they differ in precisely one coordinate. Alon proved that for any sequence $v_1,\ldots,v_b$ of $b=\lceil\frac n2\rceil$ vertices of $H(n,2)$, there is a vertex whose distance from $v_i$ is at least $b-i+1$ for all $1\leq i\leq b$. In this note, we prove that for any $q\geq 3$ and any sequence $v_1,\ldots,v_b$ of $b=\lfloor(1-\frac1q)n\rfloor$ vertices of $H(n,q)$, there is a vertex whose distance from $v_i$ is at least $b-i+1$ for all $1\leq i\leq 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.<|reference_end|>
@article{tokushige2024alon's,
    title={Alon's transmitting problem and multicolor Beck--Spencer Lemma},
    author={Norihide Tokushige},
    journal={arXiv preprint arXiv:2406.19945},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.19945},
    primaryClass={math.CO cs.IT math.IT math.OC}
}