All Articles

Faithful embeddability of graphs into Banach spaces and applications

Faithful embeddability of graphs and metric spaces into Banach spaces is pivotal to
research areas as diverse as:
-the design of approximation algorithms in theoretical computer science (sparsest cut
problem, multi-commodity flows, approximate nearest neighbor search, sketching…),
-topology (Novikov conjecture),
-noncommutative geometry (coarse Baum-Connes conjecture),
-geometric group theory (Von Neumann’s amenability, Gromov’s program).
This non-exhaustive list can be stretched at will since metric spaces, with a wide
variety of features, arise in nearly all areas of mathematics.

In this talk, I will focus on bi-Lipschitz and coarse embeddings of graphs (finite and
infinite) into Banach spaces with some desirable geometric properties. I will discuss
fundamental geometric problems of either local or asymptotic nature, in particular
purely metric characterizations of “linear” properties of Banach spaces in the spirit of
the Ribe program. One of the main goal of the talk is to present some fundamental
ideas and techniques, as well as to convey the geometric intuition behind them.