Speaker: Asaf Nachmias UC Berkeley
Time: 2007-12-03 11:00-2007-12-03 12:00
Venue: FIT Building 4-603, Tsinghua University

Abstract:

    Given a d-regular graph G on n vertices and a number p in (0,1) we obtain the random graph G_p by by independently retaining each edge with probability p and erasing it with probability 1-p. The study of this random graph is also known as Percolation theory and is motivated by questions in PhysITCS.
     The most interesting geometric quantity is the size of the largest component of the random graph. For many graphs, this size exhibits a phase transition. This means that there exists some p_c such that if p = (1-\eps) p_c then the largest component is of order log(n) and if p=(1+\eps) p_c then the largest component is of linear size. This was hown first for the complete graph by Erdos and Renyi in 1960 and by now it has been known to hold for a wide class of graphs. 
     In this talk I will review some recent results which address the geometry of the random graph at criticality, i.e., when p=p_c. The recurring theme is: if the graph is "high-dimensional" enough then critical percolation on it looks like critical percolation on the complete graph. No background knowledge will be assumed.
     Partially based on joint work with Yuval Peres. 

Short Bio:

Asaf is a mathematics graduate student in UC Berkeley under the supervision of Prof. Yuval Peres and conducting research in Probability theory and CombinatorITCS.