Metric Embeddings: Bilipschitz and Coarse Embeddings into Banach Spaces

Description

Embeddings of discrete metric spaces into Banach spaces recently became an important tool in computer science and topology. The purpose of the book is to present some of the most important techniques and results, mostly on bilipschitz and coarse embeddings. The topics include: (1) Embeddability of locally finite metric spaces into Banach spaces is finitely determined; (2) Constructions of embeddings; (3) Distortion in terms of Poincaré inequalities; (4) Constructions of families of expanders and of families of graphs with unbounded girth and lower bounds on average degrees; (5) Banach spaces which do not admit coarse embeddings of expanders; (6) Structure of metric spaces which are not coarsely embeddable into a Hilbert space; (7) Applications of Markov chains to embeddability problems; (8) Metric characterizations of properties of Banach spaces; (9) Lipschitz free spaces. Substantial part of the book is devoted to a detailed presentation of relevant results of Banach space theory and graph theory. The final chapter contains a list of open problems. Extensive bibliography is also included. Each chapter, except the open problems chapter, contains exercises and a notes and remarks section containing references, discussion of related results, and suggestions for further reading. The book will help readers to enter and to work in a very rapidly developing area having many important connections with different parts of mathematics and computer science. Preface 1 Introduction: examples of metrics, embeddings, and applications 1.1 Metric spaces: definitions and main examples 1.2 Types of embeddings: isometric, bilipschitz, coarse, and uniform 1.2.1 Isometric embeddings 1.2.2 Bilipschitz embeddings 1.2.3 Coarse and uniform embeddings 1.3 Probability theory terminology and notation 1.4 Applications to the sparsest cut problem 1.5 Exercises 1.6 Notes and remarks 1.6.1 To Section 1.1 1.6.2 To Section 1.2 1.6.3 To Section 1.3 1.6.4 To Section 1.4 1.6.5 To exercises 1.7 On applications in topology 1.8 Hints to exercises 2 Embeddability of locally finite metric spaces into Banach spaces is finitely determined. Related Banach space theory 2.1 Introduction 2.2 Banach space theory: ultrafilters, ultraproducts, finite representability 2.2.1 Ultrafilters 2.2.2 Ultraproducts 2.2.3 Finite representability 2.3 Proofs of the main results on relations between embeddability of a locally finite metric space and its finite subsets 2.3.1 Proof in the bilipschitz case 2.3.2 Proof in the coarse case 2.3.3 Remarks on extensions of finite determination results 2.4 Banach space theory: type and cotype of Banach spaces, Khinchin and Kahane inequalities 2.4.1 Rademacher type and cotype 2.4.2 Kahane-Khinchin inequality 2.4.3 Characterization of spaces with trivial type or cotype 2.5 Some corollaries of the theorems on finite determination of embeddability of locally finite metric spaces 2.6 Exercises 2.7 Notes and remarks 2.8 Hints to exercises 3 Constructions of embeddings 3.1 Padded decompositions and their applications to constructions of embeddings 3.2 Padded decompositions of minor-excluded graphs 3.3 Padded decompositions in terms of ball growth 3.4 Gluing single-scale embeddings 3.5 Exercises 3.6 Notes and remarks 3.7 Hints to exercises 4 Obstacles for embeddability: Poincaré inequalities 4.1 Definition of Poincaré inequalities for metric spaces 4.2 Poincaré inequalities for expanders 4.3 Lp-distortion in terms of constants in Poincaré inequalities 4.4 Euclidean distortion and positive semidefinite matrices 4.5 Fourier analytic method of getting Poincaré inequalities 4.6 Exercises 4.7 Notes and remarks 4.8 A bit of history of coarse embeddability 4.9 Hints to exercises 5 Families of expanders and of graphs with large girth 5.1 Introduction 5.2 Spectral characterization of expanders 5.3 Kazhdan’s property (T) and expanders 5.4 Groups with property (T) 5.4.1 Finite generation of SLn(ℤ) 5.4.2 Finite quotients of SLn(ℤ) 5.4.3 Property (T) for groups SLn(ℤ) 5.4.4 Criterion for property (T) 5.5 Zigzag products 5.6 Graphs with large girth: basic definitions 5.7 Graph lift constructions and ℓ1-embeddable graphs with large girth 5.8 Probabilistic proof of existence of expanders 5.9 Size and diameter of graphs with large girth: basic facts 5.10 Random constructions of graphs with large girth 5.11 Graphs with large girth using variational techniques 5.12 Inequalities for the spectral gap of graphs with large girth 5.13 Biggs’s construction of graphs with large girth 5.14 Margulis’s 1982 construction of graphs with large girth 5.15 Families of expanders which are not coarsely embeddable one into another 5.16 Exercises 5.17 Notes and remarks 5.17.1 Bounds for spectral gaps 5.17.2 Graphs with very large spectral gaps 5.17.3 Some more results and constructions 5.18 Hints to exercises 6 Banach spaces which do not admit uniformly coarse embeddings of expanders 6.1 Banach spaces whose balls admit uniform embeddings into L1 6.2 Banach spaces not admitting coarse embeddings of expander families, using interpolation 6.3 Banach space theory: a characterization of reflexivity 6.4 Some classes of spaces whose balls are not uniformly embeddable into L1 6.4.1 Stable metric spaces and iterated limits 6.4.2 Non-embeddability result 6.5 Examples of non-reflexive spaces with nontrivial type 6.6 Exercises 6.7 Notes and remarks 6.8 Hints to exercises 7 Structure properties of spaces which are not coarsely embeddable into a Hilbert space 7.1 Expander-like structures implying coarse non-embeddability into L1 7.2 On the structure of locally finite spaces which do not admit coarse embeddings into a Hilbert space 7.3 Expansion properties of metric spaces not admitting a coarse embedding into a Hilbert space 7.4 Exercises 7.5 Notes and remarks 7.6 Hints to exercises 8 Applications of Markov chains to embeddability problems 8.1 Basic definitions and results on finite Markov chains 8.2 Markov type 8.3 First application of Markov type to embeddability problems: Euclidean distortion of graphs with large girth 8.4 Banach space theory: renormings of superreflexive spaces, q-convexity and p-smoothness 8.4.1 Definitions and duality 8.4.2 Pisier theorem on renormings of uniformly convex spaces 8.5 Markov type of uniformly smooth Banach spaces 8.6 Applications of Markov type to lower estimates of distortions of embeddings into uniformly smooth Banach spaces 8.7 Exercises 8.8 Notes and remarks 8.9 Hints to exercises 9 Metric characterizations of classes of Banach spaces 9.1 Introduction 9.2 Proof of the Ribe theorem through Bourgain’s discretization theorem 9.2.1 Proving Bourgain’s discretization theorem. Preliminary step: it suffices to consider spaces with differentiable norm 9.2.2 First step: picking the system of coordinates 9.2.3 Second step: construction of a Lipschitz almost-extension 9.2.4 Third step: further smoothing of the map using Poisson kernels 9.2.5 Poisson kernel estimates and proofs of Lemmas 9.14 and 9.15 9.3 Test-space characterizations 9.3.1 More Banach space theory: superreflexivity 9.3.2 Characterization of superreflexivity in terms of diamond graphs 9.4 Exercises 9.5 Notes and remarks 9.5.1 Another test-space characterization of superreflexivity: binary trees 9.5.2 Further results on test-spaces 9.5.3 Further results on the Ribe program 9.5.4 Non-local properties 9.6 Hints to exercises 10 Lipschitz free spaces 10.1 Introductory remarks 10.2 Lipschitz free spaces: definition and properties 10.3 The case where dX is a graph distance 10.4 Lipschitz free spaces of some finite metric spaces 10.5 Exercises 10.6 Notes and remarks 10.7 Hints to exercises 11 Open problems 11.1 Embeddability of expanders into Banach spaces 11.2 Obstacles for coarse embeddability of spaces with bounded geometry into a Hilbert space 11.2.1 The main problem 11.2.2 Comments 11.3 Embeddability of graphs with large girth 11.4 Coarse embeddability of a Hilbert space into Banach spaces Bibliography Author index Subject index