Combinatorics Seminar

When: Sunday, November 18, 10am Where: Schreiber 309 Speaker: Nati Linial, Hebrew University Title: Local graph theory

Abstract:

Numerous application areas are generating large graphs which we wish to comprehend. Protein-protein interaction networks and social networks are just two examples. Computational complexity makes it infeasible to compute many of the more interesting graph parameters and a different approach is needed. One possible strategy is to sample small sets of vertices and observe the induced subgraphs. This suggests the question what such distributions are possible. In other words, what are the possible local views of large graphs? This leads to a number of challenging problems which I will survey.

Some of the new results that I will present are joint with Yuval Peled, Benny Sudakov, Humberto Naves and Hao Huang.