MSR/MIT Reading Group: Nati Linial, Random Simplicial Complexes

Tuesday, September 1, 2015 - 4:00pm to 6:00pm
MSR (Barton room on the first floor of 1 Memorial Drive)
Nati Linial, Dept. Of Comp. Science and Engineering, Hebrew University

Why do graphs appear in most applications of mathematics to the real world? One reason is that many large systems that we study are defined by pairwise interactions of their constituents. E.g., people in social networks, companies in trading, interacting proteins in biological systems etc. But what if the underlying interactions involve more than two parties? If you still model the situation using graphs, as people often do, this description is necessarily lossy. You can also appeal to the theory of hypergraphs where hyperedges can have any cardinality, not just two (as in graphs). Unfortunately the theory of hypergraphs is not nearly as developed as graph theory, so we focus on simplicial complexes - hypergraphs in which a subset of a hyperedge must also be a hyperedge. Simplicial complexes can be viewed geometrically and in particular a graph is just a one-dimensional simplicial complex. My main story is how we developed a theory of random d-dimensional simplicial complexes that coincides, for d=1, with Erdos and Renyi's G(n,p) theory.

It is known that the threshold for connectivity in G(n,p) is p=log n/n and the first result in this theory is that for the analogous question in d dimensions the threshold is at p=d log n/n. The next challenge was to find the high-dimensional counterpart of the phase transition of random graphs and the emergence of the giant component at p=1/n. Here the story in general dimension is more complex and we have recently finished deciphering it.

In the first half of my lecture (about one hour) I give a computer presentation of the main results in this area. After a short break I will move to a board presentation of some of the ideas in the main proofs. All the necessary background will be introduced.

My collaborators in this project are: R. Meshulam and T. Luczak and students: M. Rosenthal, L. Aronshtam and Y. Peled.