Dia da Combinatória
Data: 5/Fev/24
Local: Sala 03, Bloco 914
Palestrantes:
Horário: 10h
Título: Grafos temporais e o Teorema de Menger
Resumo: Um grafo temporal é um grafo que muda com o tempo, o que significa que, a cada timestamp, apenas um subconjunto de arestas está ativo. Esta estrutura modela várias situações da vida real, desde redes sociais até transportes públicos, tendo sido utilizada também para rastreamento de contatos durante a pandemia de COVID. Apesar da sua ampla aplicabilidade, e apesar de existir há mais de duas décadas, só recentemente esta estrutura tem recebido maior atenção por parte da comunidade teórica. Nesta palestra, discutiremos as várias adaptações possíveis do Teorema de Menger para grafos temporais, das quais apenas algumas continuam válidas neste contexto.
Horário: 11h
Título: Rotulações de grafos com restrições nas distâncias.
Resumo: Vários problemas de rotulação em grafos tem suas raízes no Problema de Atribuição de Canais de Frequência (do inglês, Channel Assignment Problem (CAP)). Neste problema, transmissores estão localizados em alguma região geográfica e é comum que alguns pares de transmissores interfiram entre si por causa da sua proximidade geográfica. O problema consiste em atribuir canais de frequências aos transmissores respeitando restrições de otimalidade que visam evitar essas interferências. Nesta palestra, abordarei a Rotulação-L(2,1), que é uma rotulação de grafos que modela uma versão restrita do CAP. Formalmente, uma Rotulação-L(2,1) de um grafo G=(V(G),E(G)) é uma função f que atribui rótulos do conjunto {0,1,...,k} aos vértices de G de modo que: (i) |f(u)-f(v)| >= 2 para quaisquer dois vértices adjacentes u,v em V(G); e (ii) |f(u)-f(v)| >= 1 para quaisquer dois vértices u e v à distância 2 entre si. A Rotulação-L(2,1) foi introduzida em 1992 por J. R. Griggs e R. K. Yeh. Nesta palestra, serão apresentados resultados sobre essa rotulação, alguns relacionados à minha pesquisa, e alguns problemas em aberto.
Horário: 14h
Título: Contando colorações de Gallai em G(n,p)
Resumo: Estudamos o número de $3$-colorações de Gallai no grafo aleatório de Erd\H os-Rényi, $G(n,p)$. Uma $3$-coloração de Gallai é uma coloração das arestas de um grafo onde cada aresta recebe uma cor no conjunto $\{1, 2, 3\}$ e não existe um triângulo arco-íris, ou seja, um triângulo no grafo em que as arestas recebam 3 cores distintas. Trivialmente, todo grafo com $E$ arestas tem no mínimo $2^E$ e no máximo $3^E$ colorações deste tipo. Agora seja $E$ a variável aleatória que expressa o número de arestas em $G(n, p)$. Mostramos que para todo $\delta > 0$ existem constantes $c$ e $C$ tais que, assimptoticamente quase sempre, para $p < cn^{-1/2}$ o número de $3$-colorações de Gallai de $G(n, p)$ é pelo menos $3^{(1-\delta)E}$, e para $p > Cn^{-1/2}$ tal número é no máximo $2^{(1+\delta)E}$.
Horário: 15h
Título: Sistemas de separação por caminhos em grafos completos
Resumo: Nesta palestra mostraremos que em qualquer grafo completo com n
vértices, há uma coleção P de (1 + o(1))n caminhos que separa fortemente
qualquer par {e,f} de arestas distintas, isto é, há um caminho em P que contém a
aresta e, mas não a aresta f, e outro caminho em P que contém a aresta f mas não
a aresta e.Além disso, para certas classes de grafos αn-regulares com n
vértices, encontramos uma coleção de (sqrt{3α + 1} - 1 + o(1))n caminhos que
separa fortemente qualquer par de arestas. Ambos os resultados são os melhores
possíveis a menos do termo o(1).
Trabalho em conjunto com Cristina Gomes Fernandes e Nicolás Sanhueza-Matamala.