[Combprob] talk today: M. Krivelevich (Tel Aviv), The Phase Transition in Site Percolation on Pseudo-Random Graphs

[Daniel Spielman]

*Time:*4:00 PM - 5:00 PM*Title:*The Phase Transition in Site Percolation on
Pseudo-Random Graphs*Speaker:*M. Krivelevich , Tel Aviv*Location:*215 LOM
*Abstract:*We establish the existence of the phase transition in site
percolation on pseudo-random *d*-regular graphs. Let *G=(V,E)* be an *(n,d,λ
)*-graph, that is, a *d*-regular graph on *n* vertices in which all
eigenvalues of the adjacency matrix, but the first one, are at most *λ* in
their absolute values. Form a random subset *R* of *V* by putting every
vertex *v* in *V* into*R* independently with probability *p*. Then for any
small enough constant*ε >0*, if *p=(1-ε )/d*, then with high probability
all connected components of the subgraph of *G* induced by *R* are of size
at most logarithmic in *n*, while for *p=(1+ε )/d*, if the eigenvalue ratio *λ
/d* is small enough as a function of *ε*, then typically *R* contains a
connected component of size at least *ε n/d* and a path of length
proportional to *ε2n/d*.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.yale.edu/pipermail/combprob/attachments/20150212/028f43dc/attachment.html