Abstract | ||
---|---|---|
Let nu(Z(m)) be the minimal number of colors enough to color the m-dimensional integer grid Z(m) so that there would be no infinite monochromatic symmetric subsets. Banakh and Protasov [3] compute nu(Z(m)) = m + 1. For the one-dimensional case this just means that one can color positive integers in red, while negative in blue, thereby avoiding an infinite monochromatic symmetric subset by trivial reason. This motivates the question what changes if we allow only colorings unlimited in both directions (in "all" directions for m > 1). In this paper we show that then nu(Z) increases in 1, whereas for higher dimensions the values nu(Z(m)) remain unaffected.Furthermore we examine the density properties of a set A subset of or equal to Z(m) that ensure the existence of infinite symmetric subsets or arbitrarily large finite symmetric subsets in A. In the case that A is a sequence with small gaps, we prove a multi-dimensional analogue of the Szemeredi theorem, with symmetric subsets in place of arithmetic progressions. A similar two-dimensional statement is known for collinear subsets (Pomerance [10]), whereas for two-dimensional arithmetic progressions even the corresponding version of van der Waerden's theorem is known to be false.We also observe that A subset of or equal to N contains arbitrarily large symmetric subsets whenever the series Sigma(ais an element ofA) 1/1 diverges (for arithmetic progressions this is the well-known unproven conjecture of Erdos). A natural two-dimensional analogue of the latter statement is false. We show a counterexample built upon Erdos's construction of a dense infinite B-2-sequence. |
Year | Venue | Field |
---|---|---|
2002 | ARS COMBINATORIA | Integer,Discrete mathematics,Combinatorics,Monochromatic color,Numerical mathematics,Van der Waerden's theorem,Counterexample,Conjecture,Mathematics,Arbitrarily large |
DocType | Volume | ISSN |
Journal | 62 | 0381-7032 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Taras O. Banakh | 1 | 9 | 7.24 |
Ya. Kmit | 2 | 0 | 0.34 |
O. V. Verbitsky | 3 | 5 | 2.00 |