Title: Trees and Markov convexity
Speaker: James R. Lee, Institute for Advanced Study
Date: November 15, 2005 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Consider the following question: Given a tree metric T (i.e. the shortest-path metric on some edge-weighted tree), when does T embed into a Hilbert space with bounded distortion? We give probabilistic, geometric, and combinatorial characterizations which involve, for instance, the relationship between the convexity of a geometric space and the wandering of Markov chains which take values in that space. This allows us to answer computational problems like: Given an n-point tree T, and some value p, find a near-optimal embedding of T into R^n under the L_p norm.
Joint work with Assaf Naor and Yuval Peres.