
Speaker Nati Linial Affiliation Hebrew University Host Yuval Peres 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 kvertex graphs is called the kprofile of G. Our two main questions are: (i) What are possible kprofiles 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 nvertex 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 [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.
