Combinatorics Seminar

When: Sunday, October 18, 10am
Where: Schreiber 309
Speaker: Nati Linial, Hebrew University
Title: Local and Local-to-Global Combinatorics


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.