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

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

References
[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

Speaker Details

Nati Linial is a Professor at the School of Computer Science and Engineering at the Hebrew University of Jerusalem. He is well known for many influential advances on the interface of Combinatorics and Computer Science. His most cited contributions include [1]-[4] below.

For more information, see http://www.cs.huji.ac.il/~nati/

Date:
Speakers:
Nati Linial
Affiliation:
Hebrew University
    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks