Colloquium: Nati Linial (HUJI) - Graph metrics

Thu, 03/01/201914:30-15:30
A finite graph is automatically also a metric space, but is there any interesting geometry to speak of? In this lecture I will try to convey the idea that indeed there is very interesting geometry to explore here. I will say something on the local side of this as well as on the global aspects. The k-local profile of a big graph G is the following distribution. You sample uniformly at random k vertices in G and observe the subgraph that they span. Question - which distributions can occur? We know some of the answer but by and large it is very open. In the global part I concentrate on the question “to what extent can a finite d-regular graph resemble the infinite d-regular tree”? I will show how this naive-sounding question leads to very difficult and fascinating problems about girth and diameter of large graphs.
The lecture will be completely elementary and should be accessible to a broad mathematical audience.