CI084 - Tópicos em Teoria do Grafos

Topicos:

• Teoria Extremal
• Métodos de Álgebra Linear
• Métodos Probabilísticos/Grafos Aleatórios

Objetivos:

Carga horária: 60 Créditos: 4 Responsável: Jair.

Bibliografia básica:

1. Graph Theory, R. Diestel.
2. Graph Theory with applications, A. Bondy e U.S.S.R. Murty.
3. Algum livro de álgebra linear. Sugestões:
   1. Linear algebra, W. Greub.
   2. Elementary linear algebra, J. Munkres.
   3. Algebra linear, K. Hoffman, R. Kunze
   4. Espaços vetoriais de dimensão finita, P. Halmos

Documentos na web:

1. Linear Algebra and applications to graphs I, L. Babai, REU'02
2. Linear Algebra and applications to graphs II, L. Babai, REU'02
3. Linear Algebra, L. Babai, REU'04
4. Notes on Linear Algebra,Bruce Ikenaga
5. Down with determinants, S. Axler
6. An elementary proof of the Perron-Frobenius theorem for non-negative symmetric matricesK.Y. Lin.
7. Notes on the perron-frobenius theory of nonnegative matrices - Mike Boyle
8. Linear Algebra, Jim Hefferon
9. Elements of Abstract and Linear Algebra, Edwin H. Connell
10. Applied Linear Algebra and Matrix Analysis, Thomas S. Shores
11. Elementary Linear Algebra Keith Matthews
12. Spectral techniques in graph algorithms, N. Alon.
13. Spectral techniques, semidefinite programs, and random graphs Amin Coja-Oghlan - Habilitationsschrift, Humboldt Universität zu Berlin.
14. Expander Graphs and their Applications, N. Linial, A. Wigderson

Sistema de avaliação

• Nota final é 90% do texto digitado e 10% participação.
• Tendo 75% de freqüência, o aluno com nota maior ou igual a 70 estará aprovado.
• Tendo 75% de freqüência, o aluno com nota maior ou igual a 40 e menor do que 70 estará habilidato a fazer a prova final.
• Em qualquer outro caso o aluno estará reprovado e será indicado se houve ou não infreqüência.
• O aluno que fizer a prova final estará aprovado apenas se a média aritmética da prova final e da média final for maior ou igual a 50.

 
Aula 01 - O Teorema de Turan para K3 

Aula 02 - O Teorema de Turan para Kp 

Aula 03 - O Teorema de Turan para Kp. Teorema de Erdos-Stone. 

Aula 04 - Coloração de vértices. 

Aula 05 - no. de independencia e numero cromatico tipicos. 

Aula 06 - matrizes. 

Aula 07 - autovalores, autovetores, multiplicidades algebrica e geometrica de autovalores. 

Aula 08 - multiplicidades algebrica e geometrica de autovalores de matrizes diagonalizaveis. 

Aula 09 - matrizes simetricas. 

Aula 10 - teorema espectral real. 

Aula 11 - teorema de Courant-Fischer. 

Aula 12 - teorema de Courant-Fischer. 

Aula 13 - teorema do entrelacamento.

Aula 14 - teorema de Perron-Frobenius. 

Aula 15 - teorema de Perron-Frobenius.

Aula 16 - Introducao teoria espectral. 

Aula 17 - autovalores, grau dos vertices, conexidade. 

Aula 18 - grafos bipartidos, limitantes para no. cromatico. 

Aula 19 - distribuicao das arestas.

Aula 20 - grafos expansores. 

Aula 21 - autovalores tipicos. 

Aula 22 - numero típico de C4 rotulados. 

Aula 23 - numero tipico de arestas.

Aula 24 - Laplaciano. 

Aula 25 - Laplaciano. 

Aula 26 - Laplaciano. 

Aula 27 - Laplaciano.