Cristiane Sato
Mestranda do DCC-IME-USP
Sexta-feira, 28 de setembro de 2007, 14:00
Anfiteatro do NUMEC-USP
Resumo:
Dados grafos G e H, um homomorfismo de G em H é uma função de V(G) em V(H) que preserva adjacências. O número de homomorfismos de G em H é denotado por hom(G, H). A função hom( . , H) é um invariante de grafos. Uma pergunta muito natural seria: quando um invariante de grafos pode ser expresso como hom( . , H) para algum grafo H?
Freedman, Lovasz e Schrijver responderam essa pergunta usando a noção de matrizes de conexão. Matrizes de conexão são matrizes indexadas pelo conjunto de todos os grafos. Cada invariante de grafos possui matrizes de conexão associadas.
O resultado de Freedman, Lovasz e Schrijver diz que um invariante de grafos pode ser expresso como um homomorfismo se, e somente se, suas matrizes de conexão são positivas semidefinidas e possuem posto limitado por uma certa função.
Neste seminário, definiremos matrizes de conexão e provaremos algumas propriedades básicas. Apresentaremos também o esquema da prova de Freedman, Lovász e Schrijver.