[Colloquium] Combinatorics & Theory Talk

[Donna Brooms]

Revised:

 Combinatorics & Theory Seminar Today:
                     Note non-standard day. 
      
Today, Thursday, May 26, 2016

Ry. 251 @ 3pm

Nathan Linial (Hebrew University)

Title: “Random simplicial complexes”

Abstract:
Random graphs have been studied for over 50 years now.  They play a prominent role in combinatorics, in theoretical computer science, in statistical mechanics and in numerous areas where graphs are used to model real life situations such as systems biology, the study of social networks and more. Graphs are clearly the ideal modeling tool in describing complicated systems that are defined by pairwise interactions, but how do you deal with systems where the basic interactions involve more than two parties? A simplicial complex is a finite collection of sets (which here are called faces) that is closed under taking subsets. Thus a graph is a a one-dimensional simplicial complex with zero-dimensional faces, usually called vertices, and one-dimensional faces, aka edges. The most thoroughly studied model of random graphs is the Erdos-Renyi G(n,p) model. Such a graph has n vertices and for every two vertices x and y we put the edge xy in the graph independently with probability p. About a decade ago Meshulam and I introduced an analogous model of random simplicial complexes and started investigating them. We seek the high-dimensional counterparts of the basic phenomena known in G(n,p) theory. By now we have revealed the analog of the p=log n/n threshold for graph connectivity and (more recently) the analog of the phase transition and the emergence of the giant component that occurs at p=1/n. Many challenges arise and often the high-dimensional picture is substantially richer than the graph-theoretic situation.  In my talk I will try to review these developments.

My collaborators are: R. Meshulam and T. Luczak, past student L. Aronshtam and current student Yuval Peled.

Host: Prof. Babai

Refreshments will be served before the talk in Ry 255. 







-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160526/5cbe8dda/attachment-0001.htm