Alon's transmitting problem and multicolor Beck--Spencer Lemma
| Autor: | Tokushige, Norihide |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 7 pages, minor correction |
| Databáze: | arXiv |
| Externí odkaz: |
|