  A nearly logarithmic lower bound on the randomized competitive ratio for the
metrical task systems problem is presented. This implies a similar lower bound
for the extensively studied k-server problem. The proof is based on Ramsey-type
theorems for metric spaces, that state that every metric space contains a large
subspace which is approximately a hierarchically well-separated tree (and in
particular an ultrametric). These Ramsey-type theorems may be of independent
interest.
