Aluno: Bruno Hideki Akamine
Orientador: Marcel Kenji de Carli Silva
Proposta de trabalho: O projeto tem como objetivo estudar grafos expansores, que usualmente são pensados como uma subclasse de grafos regulares. Parte do projeto tem como objetivo dissecar e entender uma construcão de grafos de Ramanuja, expansores otimos, utilizando como bibliografia principal a dissertacão de mestrado de Karina S. Awoki. Alem disso, pretende-se estudar resultados mais recentes, envolvendo generalizacão da nocao de grafos expansores para o caso nao regular. Grafos expansores por definicao sao familias de grafos cujo indice de expansão, menor razão entre um corte e sua margem, esta afastado de zero conforme o numero de vertices cresce. Esses grafos possuem algumas caracteristicas semelhantes a grafos aleatorios, fazendo com que ele possa ser usado para 'economizar' na utilizacao de bits aleatorios. Outro problema em que esses grafos aparecem e na criacao de codigos de correcao, ou melhor, codigos que possibilitam a indentificao e correcao de erros em mensagens recebidas, causadas por algum tipo de ruido na comunicacao.