Local Combinatorics, and Some Words on Local-to-Global Phenomena

Speaker  Nati Linial

Host  Yuval Peres

Affiliation  Hebrew University

Duration  00:56:57

Date recorded  12 August 2013

Fix a (small) integer k and let G be a graph. For every set of k vertices in G we consider the subgraph induced by it. This distribution on k-vertex graphs is called the k-profile of G. Our two main questions are: (i) What are possible k-profiles of large graphs?

  1. What global properties of G can be deduced from knowledge of its profiles? Recent progress in the domain of graph limits suggests that problem (i) is key to the study of general families of random graphs.

This in turn may prove useful in investigating big data that comes in the form of large graphs (e.g., in bioinformatics). The most outstanding open question of type (ii) is the Erdos Hajnal conjecture which posits that for every graph H there is an epsilon 0, such that in every n-vertex G which contains no induced copy of H either the clique number or the anticlique number is nε. Several open questions will be mentioned in this talk. The new results that I will present are joint with Yuval Peled, Avraham Morgenstern, Benny Sudakov, Hao Huang and Humberto Naves

[1] The geometry of graphs and some of its algorithmic applications N Linial, E London, Y Rabinovich - Combinatorica, 1995 - Springer; cited by 786

[2] Expander graphs and their applications S Hoory, N Linial, A Wigderson - Bulletin of the American Mathematical Soc., 2006 - Cited by 631

[3] Constant depth circuits, Fourier transform, and learnability N Linial, Y Mansour, N Nisan - Journal of the ACM (JACM), 1993; Cited by 484

[4] The influence of variables on Boolean functions J Kahn, G Kalai, N Linial - Foundations of Computer Science 1988 - Cited by 416

©2013 Microsoft Corporation. All rights reserved.
> Local Combinatorics, and Some Words on Local-to-Global Phenomena