• 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
 
 
Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.45.2020.tde-17082020-142800
Document
Auteur
Nom complet
Karina Suemi Awoki
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2020
Directeur
Jury
Fernandes, Cristina Gomes (Président)
Gruber, Aritanan Borges Garcia
Martin, Daniel Morgato
Titre en portugais
Árvores entrelaçadoras de polinômios e grafos de Ramanujan
Mots-clés en portugais
Esparsificador espectral
Grafos de Ramanujan
Grafos expansores
Problema de Kadison-Singer
Resumé en portugais
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.
Titre en anglais
Interlacing trees of polynomials and Ramanujan graphs
Mots-clés en anglais
Expander graphs
Kadison-Singer problem
Ramanujan graphs
Spectral sparsifier
Resumé en anglais
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.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
dissertacao.pdf (1.40 Mbytes)
Date de Publication
2020-08-18
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2021. Tous droits réservés.