Monochromatic and zero-sum sets of nondecreasing modified diameter

David Grynkiewicz ; Rasheed Sabar

The electronic journal of combinatorics, Tome 13 (2006)

Résumé

Let $m$ be a positive integer whose smallest prime divisor is denoted by $p$, and let ${\Bbb Z}_m$ denote the cyclic group of residues modulo $m$. For a set $B=\{x_1,x_2,\ldots,x_m\}$ of $m$ integers satisfying $x_1 < x_2 < \cdots < x_m$, and an integer $j$ satisfying $2\leq j \leq m$, define $g_j(B)=x_j-x_1$. Furthermore, define $f_j(m,2)$ (define $f_j(m,{\Bbb Z}_m)$) to be the least integer $N$ such that for every coloring $\Delta : \{1,\ldots,N\}\rightarrow \{0,1\}$ (every coloring $\Delta : \{1,\ldots,N\}\rightarrow {\Bbb Z}_m$), there exist two $m$-sets $B_1,B_2\subset \{1,\ldots,N\}$ satisfying: (i) $\max(B_1) < \min(B_2)$, (ii) $g_j(B_1)\leq g_j(B_2)$, and (iii) $|\Delta (B_i)|=1$ for $i=1,2$ (and (iii) $\sum_{x\in B_i}\Delta (x)=0$ for $i=1,2$). We prove that $f_j(m,2)\leq 5m-3$ for all $j$, with equality holding for $j=m$, and that $f_j(m,{\Bbb Z}_m)\leq 8m+{m\over p}-6$. Moreover, we show that $f_j(m,2)\ge 4m-2+(j-1)k$, where $k=\left\lfloor\left(-1+\sqrt{{8m-9+j\over j-1}}\right){/2}\right\rfloor$, and, if $m$ is prime or $j\geq{m\over p}+p-1$, that $f_j(m,{\Bbb Z}_m)\leq 6m-4$. We conclude by showing $f_{m-1}(m,2)=f_{m-1}(m,{\Bbb Z}_m)$ for $m\geq 9$.

Détail

DOI : 10.37236/1054

Classification : 05D05, 11B75
Mots-clés : cyclic group, coloring