• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
https://doi.org/10.11606/D.45.2020.tde-17082020-142800
Documento
Autor
Nome completo
Karina Suemi Awoki
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2020
Orientador
Banca examinadora
Fernandes, Cristina Gomes (Presidente)
Gruber, Aritanan Borges Garcia
Martin, Daniel Morgato
Título em português
Árvores entrelaçadoras de polinômios e grafos de Ramanujan
Palavras-chave em português
Esparsificador espectral
Grafos de Ramanujan
Grafos expansores
Problema de Kadison-Singer
Resumo em português
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.
Título em inglês
Interlacing trees of polynomials and Ramanujan graphs
Palavras-chave em inglês
Expander graphs
Kadison-Singer problem
Ramanujan graphs
Spectral sparsifier
Resumo em inglês
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.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
dissertacao.pdf (1.40 Mbytes)
Data de Publicação
2020-08-18
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2021. Todos os direitos reservados.