<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<br>
<meta charset="utf-8">
<table style="color: rgb(0, 0, 0); font-family: Geneva, Arial,
Helvetica, sans-serif; font-size: 12px; font-style: normal;
font-variant: normal; font-weight: normal; letter-spacing: normal;
line-height: normal; orphans: auto; text-align: left; text-indent:
0px; text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px;" border="0" cellpadding="0"
cellspacing="0" width="100%">
<tbody>
<tr>
<td class="colloq" style="font-size: 12px; padding-top: 5px;
padding-bottom: 5px;"><strong>Date:</strong><span
class="Apple-converted-space"> </span><a name="200912"
id="200912"></a>April 29, Fine Hall 214, 4:30 pm<br>
</td>
</tr>
<tr>
<td class="colloq" style="font-size: 12px; padding-top: 5px;
padding-bottom: 5px;"><strong>Speaker:</strong><span
class="Apple-converted-space"> </span>Daniel Spielman,
Yale University</td>
</tr>
<tr>
<td class="colloq" style="font-size: 12px; padding-top: 5px;
padding-bottom: 5px;"><strong>Title:<span
class="Apple-converted-space"> </span></strong>A good
lift: bipartite Ramanujan graphs of all degrees</td>
</tr>
<tr>
<td class="colloq" style="font-size: 12px; padding-top: 5px;
padding-bottom: 5px;"><strong>Abstract:</strong><span
class="Apple-converted-space"> </span>We prove that there
exist infinite families of bipartite Ramanujan graphs of
every degree bigger than 2. We do this by proving a variant
of a conjecture of Bilu and Linial about the existence of
good 2-lifts of every graph. We also construct infinite
families of `irregular Ramanujan' graphs, whose eigenvalues
are bounded by the spectral radius of their universal cover.
In particular, we construct infinite families of
(c,d)-biregular bipartite Ramanujan graphs for all c and d
greater than 2. Our proof exploits a new technique for
demonstrating the existence of useful combinatorial objects
that we call the ``Method of Interlacing Polynomials''. The
proofs are elementary, and the talk should be accessible to
a broad audience. Joint work with Adam Marcus and Nikhil
Srivastava.</td>
</tr>
</tbody>
</table>
<br>
</body>
</html>