Interlacing trees of polynomials and Ramanujan graphs

Este trabalho tem como objetivo o estudo de grafos expansores, em particular, o estudo de técnicas de construção de famílias infinitas de grafos de Ramanujan regulares e de bons esparsificadores espectrais de grafos completos, ambos considerados bons grafos expansores. Dentre essas técnicas, estão a utilização de árvores entrelaçadoras de polinômios e a construção de grafos com funções barreira que limitam o crescimento de seus autovalores. Também estudaremos uma prova recente da resolução do Problema de Kadison-Singer por Marcus, Spielman e Srivastava, que utiliza uma combinação das técnicas de construção de bons expansores citadas anteriormente.The goal of this work is to study expander graphs, particularly techniques to construct infinite families of (regular) Ramanujan graphs and spectral sparsifiers of complete graphs, both considered good expander graphs. Among these techniques are the use of interlacing trees of polynomials and the construction of graphs using barrier functions to bound eigenvalue growth. We also study a recent proof of the resolution of the Kadison-Singer Problem due to Marcus, Spielman, and Srivastava, which uses a combination of the previously mentioned techniques for constructing good expanders