Matrizes de Conexão e Homomorfismos de Grafos I

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.