























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 (1992) 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 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).
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。