95-54 On a Metric Generalization of Ramsey's Theorem

DIMACS TR: 95-54

On a Metric Generalization of Ramsey's Theorem

Authors: Pal Erdos, Andras Hajnal, Janos Pach

ABSTRACT
An increasing sequence of reals $x=\langle x_i: i < \omega\rangle$ is simple if all ``gaps'' $x_{i+1}-x_i$are different. Two simple sequences $x$ and $y$ are distance similar if $x_{i+1}-x_i < x_{j+1}-x_j$ if and only if $y_{i+1}-y_i < y_{j+1}-y_j$ for all $i$ and $j$. Given any bounded simple sequence $x$ and any coloring of the pairs of rational numbers by a finite number of colors, we prove that there is a sequence $y$ distance similar to $x$ all of whose pairs are of the same color. We also consider many related problems and generalizations.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-54.ps.gz

DIMACS Home Page