============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Vértices do corpo teta de um grafo no espaço 
             de matrizes
            
Palestrante: Marcel Kenji de Carli Silva
             Universidade de São Paulo

Hora e Data: 14h, sexta-feira, 9 de maio de 2014

Local:       Sala Multi-usos do Numec

Resumo:

Nesta  palestra,  discutirei   alguns  aspectos  básicos  da
estrutura facial de  programas semidefinidos, enfatizando as
diferenças   com  faces   de   programas  lineares.   Nenhum
conhecimento  prévio  sobre  programação  semidefinida  será
assumido.

A  seguir,   apresentarei  uma  caracterização,   obtida  em
colaboração com  Levent Tunçel,  dos vértices do  corpo teta
elevado  de  um  grafo   G,  que  descrevemos  no  parágrafo
seguinte.  Esses   vértices  correspondem  precisamente  aos
conjuntos estáveis de G.

O  corpo  teta  de  um  grafo G  é  uma  clássica  relaxação
semidefinida  do  politopo  dos  conjuntos  estáveis  de  G,
baseada na celebrada função teta de Lovász. Essa relaxação é
a projeção  de um conjunto convexo, num  espaço de matrizes,
que é a região  viável de um programa semidefinido. Chamamos
tal conjunto  de matrizes  de "corpo teta  elevado de  G". A
tratabilidade  do corpo teta  de G  depende fundamentalmente
dessa representação.