Speaker Nati Linial
Affiliation Hebrew University
Host Yuval Peres
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?
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
 Expander graphs and their applications S Hoory, N Linial, A Wigderson - Bulletin of the American Mathematical Soc., 2006 - Cited by 631
 Constant depth circuits, Fourier transform, and learnability N Linial, Y Mansour, N Nisan - Journal of the ACM (JACM), 1993; Cited by 484
 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.