<div dir="ltr"><table width="100%" cellpadding="5" cellspacing="0" border="0" style="font-family:Times"><tbody><tr><td valign="top" align="right" bgcolor="#FFFFFF"><font face="Verdana,Arial,Helvetica" size="-1" color="#001084"><b>Time:</b></font></td><td valign="top" align="left" bgcolor="#FFFFFF"><font face="Verdana,Arial,Helvetica" size="-1">4:00 PM - 5:00 PM</font></td></tr><tr><td valign="top" align="right" bgcolor="#FFFFFF"><font face="Verdana,Arial,Helvetica" size="-1" color="#001084"><b>Title:</b></font></td><td valign="top" align="left" bgcolor="#FFFFFF"><font face="Verdana,Arial,Helvetica" size="-1">The Phase Transition in Site Percolation on Pseudo-Random Graphs</font></td></tr><tr><td valign="top" align="right" bgcolor="#FFFFFF"><font face="Verdana,Arial,Helvetica" size="-1" color="#001084"><b>Speaker:</b></font></td><td valign="top" align="left" bgcolor="#FFFFFF"><font face="Verdana,Arial,Helvetica" size="-1">M. Krivelevich , Tel Aviv</font></td></tr><tr><td valign="top" align="right" bgcolor="#FFFFFF"><font face="Verdana,Arial,Helvetica" size="-1" color="#001084"><b>Location:</b></font></td><td valign="top" align="left" bgcolor="#FFFFFF"><font face="Verdana,Arial,Helvetica" size="-1">215 LOM<br></font></td></tr><tr><td colspan="2" valign="top" align="left" bgcolor="#FFFFFF"><font face="Verdana,Arial,Helvetica" size="-1" color="#001084"><b>Abstract:</b></font></td></tr><tr><td colspan="2" valign="top" align="left" bgcolor="#FFFFFF"><font face="Verdana,Arial,Helvetica" size="-1">We establish the existence of the phase transition in site percolation on pseudo-random <i>d</i>-regular graphs. Let <i>G=(V,E)</i> be an <i>(n,d,λ )</i>-graph, that is, a <i>d</i>-regular graph on <i>n</i> vertices in which all eigenvalues of the adjacency matrix, but the first one, are at most <i>λ</i> in their absolute values. Form a random subset <i>R</i> of <i>V</i> by putting every vertex <i>v</i> in <i>V</i> into<i>R</i> independently with probability <i>p</i>. Then for any small enough constant<i>ε &gt;0</i>, if <i>p=(1-ε )/d</i>, then with high probability all connected components of the subgraph of <i>G</i> induced by <i>R</i> are of size at most logarithmic in <i>n</i>, while for <i>p=(1+ε )/d</i>, if the eigenvalue ratio <i>λ /d</i> is small enough as a function of <i>ε</i>, then typically <i>R</i> contains a connected component of size at least <i>ε n/d</i> and a path of length proportional to <i>ε²n/d</i>.</font></td></tr></tbody></table><p style="color:rgb(0,0,0);font-family:Times;font-size:medium;text-align:-webkit-center"></p><center style="color:rgb(0,0,0);font-family:Times;font-size:medium"><br><form name="form1" method="post"><br></form></center></div>