1º Workshop Brasileiro de Combinatória

Programação

O Workshop Brasileiro de Combinatória contará com uma programação diversa que tem como objetivo agregar tanto estudantes sem experiência na área quanto pesquisadores de áreas correlatas e especialistas para resolução de problemas. A programação é composta de quatro atividades:

• Palestras plenárias – As palestras plenárias serão ministradas em português, oferecendo uma visão aprofundada e acessível de pesquisas atuais. Essas apresentações também proporcionam um ambiente de aprendizado, motivando os estudantes a se envolverem em projetos de pesquisa e estudos mais avançados.

• Minicurso Introdutório – Consiste na oferta de um curso introdutório em Combinatória, especialmente direcionado para alunos de graduação e pós-graduação. Esse curso fornecerá uma base para o estudo da Combinatória, abrangendo conceitos fundamentais e métodos de resolução de problemas (com sessões monitoradas por estudantes mais experientes).

• Mesa Redonda – Com o propósito de discutir as possibilidades e oportunidades em Combinatória, tanto no Brasil quanto no exterior, convidamos três pesquisadores da área com carreiras e formações distintas para fazerem parte da nossa mesa redonda. Essa interação direta com os especialistas será uma oportunidade única para os participantes esclarecerem dúvidas, receberem conselhos e obterem inspiração para seguir carreiras na área.

• Sessões de trabalho em grupo – Espaço destinado aos estudantes mais avançados ou pesquisadores interessados em trabalhar na pesquisa e solução de problemas em abertos na área de Combinatória.

Teremos também atividades culturais no fim de cada dia do evento (mais informações a cerca das atividades cuturais podem ser encontradas aqui).

A seguir, temos os horários das atividades.

Plenária 1

Título: Decomposições de grafos em caminhos

Palestrante: Fábio Happ Botler (USP)

Resumo: Uma decomposição de um grafo $G$ em caminhos é uma família de caminhos aresta-disjuntos de $G$ que cobre o conjunto de arestas de $G$. Neste seminário estamos interessados em decomposições com o menor número de caminhos. Em particular, estamos interessados na Conjectura de Gallai que diz que todo grafo com $n$ vértices pode ser decomposto em no máximo $(n+1)/2$ caminhos. Veremos alguns resultados interessantes nesta direção, bem como algumas provas, como por exemplo, o teorema de Lovász (1968), que diz que todo grafo com $n$ vértices pode ser decomposto em no máximo $n-1$ caminhos; um resultado de Pyber (1996) que diz que um tal grafo pode ser decomposto em no máximo $n/2$ caminhos contanto que não contenha um ciclo induzido por vértices de grau par; e um resultado de Dean e Kouider (2000) que melhora o limitante superior obtido por Lovász para $2n/3$.

Plenária 2

Título: Colorações ímpares e livre-de-conflitos

Palestrante: Carla Negri Lintzmayer (UFABC)

Resumo: O número cromático livre-de-conflitos de um grafo $G$, $\chi_{\mathrm{pcf}}(G)$, é o menor inteiro positivo $k$ tal que $G$ tem uma $k$-coloração própria na qual para todo vértice não isolado existe uma cor que aparece exatamente uma vez na sua vizinhança. O número cromático ímpar de um grafo $G$, $\chi_{\mathrm{o}}(G)$, é o menor inteiro positivo $k$ tal que $G$ tem uma $k$-coloração própria na qual para todo vértice não isolado existe uma cor que aparece um número ímpar de vezes na sua vizinhança. Note que vale $\chi(G)\leq \chi_{\mathrm{o}}(G) \leq \chi_{\mathrm{pcf}}(G)$. Enquanto colorações próprias (vértices vizinhos não podem ter a mesma cor), esses parâmetros foram introduzidos bem recentemente (2022 e 2023). Nessa apresentação mostraremos alguns resultados sobre limitantes superiores para os valores dos números cromáticos livre-de-conflitos e ímpar de algumas classes de grafos. Esses resultados fazem parte de um trabalho em conjunto com A. Jiménez, K. Knauer, M. Matamala, J. P. Peña, D. A. Quiroz, M. Sambinelli, Y. Wakabayashi, W. Yu, e J. Zamora

Plenária 3

Título: Cortes máximos: um encontro de combinatória, otimização contínua e probabilidade

Palestrante: Cristiane Maria Sato (UFABC)

Resumo: Iremos apresentar uma relação de dualidade entre o problema da cobertura fracionária com pesos e o problema do corte máximo com pesos. Isso nos permite estender o clássico algoritmo de Goemans e Williamson para aproximar simultaneamente instâncias desses dois problemas e fornecer um certificado para a qualidade das soluções obtidas. Nesta palestra, iremos apresentar um histórico sobre o problema do corte máximo e da evolução dos métodos utilizados. Este é um trabalho conjunto com N. Benedetto Proença, M. K. de Carli Silva e L. Tunçel.

Plenária 4

Título: Resultados recentes acerca do problema de separação por caminhos

Palestrante: Guilherme Oliveira Mota (USP)

Resumo: Discutiremos o problema de separar as arestas de um grafo utilizando poucos caminhos, um problema clássico que vem ganhando muita atenção recentemente. Dado um grafo, o objetivo é encontrar uma família pequena de caminhos tal que, para qualquer par de arestas ${e,f}$, há um caminho que contém a aresta $e$, mas não contém a aresta $f$, e outro caminho que contém a aresta $e$, mas não contém a aresta $f$. Apresentaremos as ideias envolvidas em alguns resultados recentes envolvendo esse problema e daremos algumas direções de pesquisa possíveis.

Minicurso

Título: Introdução ao Método Probabilístico e Grafos Aleatórios

Ministrante: Taísa Lopes Martins (UFF)

Monitora: Alicia Maria do Nascimento Amorim (UFF)

Resumo: O método probabilístico é uma ferramenta extremamente poderosa e não construtiva, com aplicações primárias na combinatória (extremal), mas também com sucesso em diversas outras áreas da matemática, como teoria dos números, álgebra linear e análise real, além de ser amplamente utilizado na ciência da computação teórica, por exemplo em algoritmos aleatórios. Ele é empregado para demonstrar a existência de um objeto com determinadas propriedades sem necessariamente encontrá-lo. Um grafo aleatório é aquele gerado por algum processo aleatório. A teoria dos grafos aleatórios está na interseção entre a teoria dos grafos e a teoria da probabilidade, analisando as propriedades típicas desses grafos.

Neste minicurso introduziremos ferramentas padrões dos tópicos abordados que podem ser imediatamente aplicadas para resolver problemas em aberto de diversas áreas da matemática, tanto puras quanto aplicadas. Nosso foco estará em conceitos e técnicas de combinatória extremal, permitindo que os alunos se familiarizem com os princípios fundamentais, uma ampla gama de resultados e métodos clássicos, bem como tópicos contemporâneos de pesquisa.

Mesa redonda

Título: Quais os caminhos para a formação de pesquisadores em combinatória? Uma perspectiva tanto da matemática quanto da computação

Participantes: Diana Sasaki Nobrega (UERJ), Cláudia Linhares Sales (UFC) e Luz Paulo Freire Moreira (UFPE).