×

Monochromatic and zero-sum sets of nondecreasing modified diameter. (English) Zbl 1084.05073

Summary: Let \(m\) be a positive integer whose smallest prime divisor is denoted by \(p\), and let \({\mathbb Z}_m\) denote the cyclic group of residues modulo \(m\). For a set \(B=\{x_1,x_2,\dots,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,{\mathbb Z}_m)\)) to be the least integer \(N\) such that for every coloring \(\Delta : \{1,\ldots,N\}\rightarrow \{0,1\}\) (every coloring \(\Delta : \{1,\dots,N\}\rightarrow {\mathbb Z}_m\)), there exist two \(m\)-sets \(B_1,B_2\subset \{1,\dots,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,{\mathbb Z}_m)\leq 8m+{m\over p}-6\). Moreover, we show that \(f_j(m,2)\geq 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,{\mathbb Z}_m)\leq 6m-4\). We conclude by showing \(f_{m-1}(m,2)=f_{m-1}(m,{\mathbb Z}_m)\) for \(m\geq 9\).

MSC:

05D05 Extremal set theory
11B75 Other combinatorial number theory
PDF BibTeX XML Cite
Full Text: EuDML EMIS