Speaker: Manor Mendel (Hebrew University)

Title: On Metric Ramsey-Type Phenomena: 
       Lower Bounds for Distortions Greater than 2.

Abstract:
---------
The main question in this talk may be viewed as a non-linear analog of
Dvoretzky's Theorem in Banach space theory or as part of Ramsey Theory in
combinatorics. Given a finite metric space X and alpha>1, we seek the
largest cardinality of a subset of X which may be embedded with distortion
alpha in Hilbert space. We provide nearly tight upper and lower bounds on
this cardinality in terms of the cardinality of X and alpha. Among other
things it is shown that this quantity exhibits a clear phase transition at
alpha=2, and for alpha>2 it behaves as n^{C(alpha)}, where C(alpha) tends 
to 1 as alpha tends to infinity. 

We also study the particular cases where X is the discrete cube, or the
metric of an expander graph. I will concentrate on proving lower bounds
when alpha>2. 

Joint work with Yair Bartal, Nati Linial, and Assaf Naor.