============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Eigenvalues of random lifts of graphs

            
Palestrante: Simon Richard Griffiths
             IMPA

Hora e Data: 15h30m, sexta-feira, 29 de setembro de 2010

Local:       auditório do NUMEC

Resumo:

The  expansion properties  of  a $d$-regular  graph $G$  are
closely related  its spectrum.  For  this reason there  is a
lot  of   interest  in  putting  bounds   on  the  parameter
\lambda(G),  defined   to  be  the  maximum   modulus  of  a
non-trivial eigenvalue of G.   We consider this question for
random lifts of graphs.  Given  a fixed d-regular graph H, a
random n-lift G of H is obtained by replacing each vertex of
H  by  n  vertices  and  each edge  by  a  random  matching.
Lubetzky,  Sudakov and Vu  recently proved  that \lambda(G)=
O((\lambda(H)  \vee \sqrt{d})\log{d}) with  high probability
(as  n \to  \infty).   We improve  on  this result,  proving
\lambda(G)=O(\sqrt{d})    \vee    \lambda(H)    with    high
probability.