Combinatorics Seminar
When: Sunday, October 18, 10am
Where: Schreiber 309
Speaker: Nati Linial, Hebrew University
Title: Local and Local-to-Global Combinatorics
Abstract:
In many current application areas much of the data comes in the
form
of very large graphs. It is a pressing practical problem what to
do
with such data. Unfortunately there is presently no satisfactory
mathematically justified answer to this question and so people
resort to various heuristics of questionable value. In this
lecture
I will describe some initial steps in this direction. This
approach
is based on the premise that we are able to probe the big graph
locally and get a good idea about its local structure. To set up
a general framework for our work I will briefly explain some of
the basic findings in the theory of graph limits (Lovász, Szegedy
and several coauthors). I will then turn to two major problems
that
this line of research naturally suggests: (i) What are the
possible
k-profiles of large graphs (k is a fixed small integer). (ii) What
global properties of a large graph can be inferred from its
k-profiles.
I will mention several of the many problems that remain open in
this field.