Seminários TCCO

2022

Neste semestre os seminários estão acontecendo no Auditório Imre Simon (CCSL).

  • Carla Negri Lintzmayer (UFABC)
  • Data: 27/10 – 14h – LOCAL: Sala B016 (IME – Bloco B)

Título: Arborescências folhudas em DAGs

Resumo: Este seminário resume os principais resultados que obtivemos em algoritmos de aproximação para o problema de encontrar árvores geradoras com número máximo de folhas em digrafos acíclicos, uma \(3/2\)-aproximação e uma \(7/5\)-aproximação, o que envolve a relação deste com outros problemas interessantes (emparelhamentos e conjuntos independentes).
Trabalho em conjunto com Cristina G. Fernandes.


  • Victor Sanches Portella (University of British Columbia)
  • Data: 21/10 – 14h

Título: Quando Online Learning encontra Cálculo Estocástico

Resumo: Online learning (OL) é um modelo teórico de aprendizado de máquina que relaxa as hipóteses típicas feitas sobre a fonte de dados. Um dos casos mais fundamentais de OL é o problema de predição com ajuda de experts. Nele, um jogador tem que fazer uma sequência de predições, por exemplo, predizer a cada dia se choverá ou não no dia seguinte. Ao invés de fazer a predição sem nenhuma informação, o jogador tem acesso a dicas de um conjunto de experts. Em cada rodada, o jogador escolhe um dos experts, possivelmente de forma aleatorizada, cuja sugestão ele vai seguir. Depois de cada escolha do jogador, um adversário decide quais experts estavam certos. Mesmo com a natureza adversarial desse modelo, existem estratégias que permitem o jogador de certa forma predizer tão bem quanto o melhor dos experts. Para além de OL, esse problema tem aplicações em várias áreas, tais como boosting, otimização combinatória, privacidade, dentre outras.

O problema dos experts é um clássico de OL. No entanto, ainda existem perguntas em aberto sobre ele. Por exemplo: será que um jogador que sabe de antemão o número de predições que terá que fazer no total é um melhor preditor do que um que não tem essa mesma informação? Essa pergunta nos levou a estudar uma versão do problema dos experts em que, ao invés de uma sequência discreta de decisões, o jogador faz uma predição em todo instante de tempo de forma contínua. Nesta palestra, farei uma breve introdução ao problema dos experts e algumas de suas aplicações. Em seguida, discutirei o modelo com tempo contínuo, como podemos desenvolver estratégias para o jogador usando cálculo estocástico, e como podemos em alguns casos transferir esses algoritmos e resultados de volta ao caso discreto.

Parte desse trabalho foi em conjunto com Nick Harvey, Chris Liaw, e Laura Greenstreet.


  • Cláudio Lucchesi (USP)
  • Data: 07/10 – 14h

Título: Grafos cobertos por emparelhamentos

Resumo: Um grafo é coberto por emparelhamentos (gce) se é conexo e toda aresta pertence a um emparelhamento perfeito. Os grafos cúbicos 2-aresta-conexos são todos cobertos por emparelhamentos. Os exemplos mais ilustres de gce são o $K_4$, o prisma triangular e o grafo de Petersen.

A origem desse estudo está no final do século 19, com o então Problemas das 4 cores. Mas recentemente tem havido muito progresso, com teoremas bonitos e conjecturas atraentes. Em particular há um teorema, cuja demonstração, do Lovász, com certeza está no livro de Deus de Erdős.

Pretendemos dar uma amostra da área para degustação, também com apresentação de alguns problemas em aberto e conjecturas interessantes.

Em coautoria com U. S. R. Murty, estamos prestes a enviar para publicação o livro “Perfect Matchings: A Theory of Matching Covered Graphs”.

Outro livro básico na área é o livro de Lovász e Plummer, “Matching Theory”.


Título: O número cromático abstrato

Resumo: Qual é a densidade de um grafo que garante que ele conterá uma cópia de um subgrafo em particular? Ou que ele conterá um subgrafo em uma família \(\mathcal{F}\) ? O célebre Teorema de Erdős–Stone–Simonovits caracteriza a densidade máxima de grafos livres de cópias de \(\mathcal{F}\) em termos do mínimo dos números cromáticos dos grafos em \(\mathcal{F}\). Recentemente, generalizações desse teorema para grafos ordenados, grafos ciclicamente ordenados, grafos com arestas ordenadas, etc. foram provadas em termos de variantes do número cromático.

Em um trabalho recente com A. Razborov, um resultado análogo desse teorema foi provado no contexto de “grafos com estrutura extra arbitrária” (formalmente, esse contexto é capturado por interpretações abertas da teoria de grafos em uma teoria universal de primeira-ordem \(T\)) em termos de um número cromático abstrato. Porém, como o nome sugere, a primeira fórmula para tal número cromático abstrato é tão abstrata que sua computabilidade foi deixada como problema aberto.

Nesta palestra, apresentarei essa generalização do teorema de Erdős–Stone–Simonovits, e uma fórmula alternativa para o número cromático abstrato que se baseia em uma versão partida do teorema de Ramsey. Uma consequência de tal fórmula alternativa é a computabilidade do número cromático abstrato quando a teoria universal \(T\) subjacente é finitamente axiomatizável.

Esta palestra não requererá nenhum conhecimento prévio.