Aluno: Bruno Hideki Akamine
Orientador: Marcel K. de Carli Silva
The goal of this project is to study generalizations of expander graphs and prove two Alon-Boppana type bounds for them. The first generalization covered uses the notion of spectral sparsifiers and we consider as expanders the spectral sparsifiers of the complete graph. The second generalization uses the normalized Laplacian matrix of unweighted graphs which do not need to be regular. The prove of such bounds utilizes some interesting concepts such as non backtracking walks.
keywords: Spectral Graph Theory, Expander Graphs, Spectral Sparsifier, Laplacian matrix
MonographPoster