O Seminário de Combinatória continua suas atividades de forma online. Agradecemos a oportunidade de receber o Prof. Gabriel Coutinho, da Universidade Federal de Minas Gerais (UFMG).
Emitiremos certificados de participação para Atividade Complementar. Basta colocar seu nome completo, instituição de origem e e-mail no chat ao final do seminário.
Não é necessária inscrição prévia.
Data: 23/09/2026
Horário: 14h (Brasil)
Sala: https://meet.google.com/tgj-
Palestrante: Gabriel Coutinho, Universidade Federal de Minas Gerais (UFMG)
Título: Sinais, conflitos e theta
Resumo:
Um conjunto de vértices de um grafo cujas arestas têm sinal é balanceado quando o subgrafo induzido não contém ciclos negativos. Essa noção leva a problemas de coloração e de máximo subgrafo induzido que incluem, como casos particulares, conjuntos estáveis e subgráfos bipartidos induzidos.
Nesta palestra, construiremos o grafo conflito, que traduz subconjuntos balanceados em conjuntos independentes, e usaremos homomorfismos para motivar uma versão com sinal do parâmetro de Lovász theta. O parâmetro escalar reduz-se ao theta de um grafo ordinário, mas o theta body projetado preserva uma estrutura genuinamente signed.
Terminaremos com uma noção de perfeição balanceada e com o problema de caracterizá-la.
Baseado em:
Gabriel Coutinho, A Lovász Theta Parameter and Theta Body for Signed Graphs, arXiv:2608.01716.
Convidamos toda a comunidade a participar.
Contamos com sua presença.