Videos

Low-Distortion Embeddings of Graphs with Large Girth

Presenter
October 18, 2011
SLMath
Keywords:
  • Banach space
  • girth
  • expander graph
  • embedding theorems
  • geometric group theory
  • L^1 optimization
MSC:
  • 46-xx
  • 46Bxx
  • 46B20
  • 54C25
  • 05C75
  • 05C12
  • 05C78
  • 05Cxx
Low-Distortion Embeddings of Graphs with Large Girth Thumbnail
Play Video
Abstract
The main purpose of the talk is to present a construction of a sequence of k-regular graphs, k>2, with indefinitely growing girths admitting embeddings into L_1 with uniformly bounded distortions. This result solves the problem posed by N. Linial, A. Magen, and A. Naor (2002).
Abstract