Seminários TCCO | Teoria da Computação, Combinatória e Otimização

2024

Seminários – Problemas de separação por caminhos

Teremos alguns seminários sobre resultados recentes acerca do problema de separação por caminhos. Serão apresentados os resultados descritos nos seguintes trabalhos:
– https://arxiv.org/abs/2301.08707
– https://arxiv.org/abs/2312.14879
– https://arxiv.org/abs/2403.08210

Guilherme Mota (USP)
19/4 (sexta-feira) – 14h – Local: A249 (Bloco A)

Título: Sistemas de separação por caminhos em grafos completos

Resumo: 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 contém a aresta $f$, e outro caminho em $P$ que contém a aresta $f$ mas não contém a aresta $e$. Além disso, para certas classes de grafos $\alpha n$-regulares com $n$ vértices, encontramos uma coleção de $ (\sqrt{3\alpha + 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.

Fábio Botler (USP)
12/4 (sexta-feira) – 14h – Local: Auditório Jacy Monteiro (Bloco A)

Título: Separating the edges of a graph by a linear number of paths

Resumo: Recently, Letzter proved that any graph of order $n$ contains a collection of $O(n\log^{\star} n)$ paths with the following property: for all distinct edges $e$ and $f$ there exists a path $\mathcal{P}$ in which contains $e$ but not $f$. We improve this upper bound to $19n$, thus answering a question of G.O.H. Katona and confirming a conjecture independently posed by Balogh, Csaba, Martin, and Pluhár and by Falgas-Ravry, Kittipassorn, Korándi, Letzter, and Narayanan. Our proof is elementary and self-contained.

Joint work with Marthe Bonamy, François Dross, Tássio Naia and Jozef Skokan

Vinicius Fernandes dos Santos (UFMG)
13/3 (quarta-feira) – 14h – Local: Auditório Imre Simon (IME – CCSL)

Título: Jogos, Quebra-Cabeças e Complexidade Computacional

Resumo: Muitos jogos e quebra-cabeças atraem o interesse de pessoas em busca de desafios intelectuais. De certa forma, a dificuldade de uma atividade ajuda a torná-la instigante: um quebra-cabeça muito simples rapidamente se torna desinteressante. Frequentemente tal dificuldade pode ser formalizada, permitindo demonstrar que tais jogos também são difíceis, em diferentes níveis, até mesmo para modelos computacionais.
O estudo da dificuldade de jogos acompanhou os avanços da complexidade computacional, não só utilizando as ferramentas já existentes para a determinação da dificuldade de certos jogos, mas também motivando o desenvolvimento e formalização de novas ideias e modelos.
Nesta palestra discutiremos jogos conhecidos e como diferentes jogos, alguns conhecidos e outros artificiais, se posicionam em diversas classes de complexidade, não apenas nas famosas classes P e NP, mas também em classes mais gerais, como PSPACE e EXP.

Marcelo Campos (Universidade de Cambridge)
8/3 (sexta-feira) – 14h – Local: Sala B03 (IME – Bloco B)

Título: A new lower bound for sphere packing

Resumo: We show there exists a packing of identical spheres in $\mathbb{R}_d$ with density at least \[(1−o(1))\frac{d\log d}{2d+1}\] as $d\to\infty$. This improves upon previous bounds for general $d$ by a factor of order $\log d$ and is the first asymptotically growing improvement to Rogers’ bound from 1947.

Joint work with Matthew Jenssen, Marcus Michelen, Julian Sahasrabudhe.

2023

Marcelo Campos (Universidade de Cambridge)
15/12 (sexta-feira) – 15h – Local: Auditório Jacy Monteiro (IME – Bloco B)

Título: Número de independência de grafos de Cayley mais esparsos

Resumo: Dado $A \subseteq \mathbb{Z}n$ $p$-aleatório, o grafo de Cayley aleatório $\Gamma_p$ é definido com tendo vértices $\mathbb{Z}_n$ e uma aresta entre $x, y \in \mathbb{Z}_n$ se $x + y \in A$. Para $p=1/2$, Green e Morris mostraram que o número de independência de $\Gamma{1/2}$ é assintoticamente igual a $\alpha(G(n, 1/2))$, com alta probabilidade. Neste seminário vou mostrar que o número de independência de $\Gamma_p$ se iguala ao de $G(n,p)$ para $p \geq (\log n)^{-1/80}$.

Trabalho em conjunto com Lucas Aragão, Gabriel Dahia e João Pedro Marciano.

Nathan Benedetto Proença (Universidade de Waterloo)
22/09 (sexta-feira) – 14h – Local: Sala A241 (IME – Bloco A)

Título: The Goemans and Williamson Algorithm Extended to the Weighted Fractional Cut-Covering Problem

Resumo: A fractional cut cover is a weighted collection of cuts in a graph covering each edge at least once. The fractional cut-covering problem is to compute, given an input graph, the smallest (total) weight of a fractional cut cover. We study a generalization of this problem, where one can parametrize how many times each edge must be covered. This generalization is tied to the maximum cut problem via convex duality. This relationship affords a primal-dual extension of the celebrated work of Goemans and Williamson. We develop algorithms producing not only approximately optimal fractional cut covers, but also simultaneously certifying optimality of fractional cut-covering and maximum cut instances.

This is joint work with Marcel K. de Carli Silva (USP), Cristiane Sato (UFABC), and Levent Tunçel (University of Waterloo).

Walner Mendonça (USP)
01/09 (sexta-feira) – 14h – Local: Sala A241 (IME – Bloco A)

Título: Ramsey-bondade em grafos densos

Resumo: Dizemos que um grafo $G$ é Ramsey para o par de grafos $(F,H)$, se em toda coloração das arestas de $G$ com as cores vermelho e azul, existe uma cópia vermelha de $F$ ou uma cópia azul de $H$. Chvátal mostrou que o grafo completo $K_n$ é Ramsey para o par $(K_r,P_t)$, para $n \geq (r-1)(t-1) + 1$. Neste seminário, generalizaremos o teorema de Chvátal mostrando que para qualquer grafo $G$ com $n=(r-1)(t-1) + 1$ vértices e $\delta(G)\geq n – t/2$, temos que $G$ é Ramsey para $(K_r,P_t)$. Com este resultado, iniciamos o estudo de Ramsey-bondade em grafos densos.

Trabalho em conjunto com Lucas Aragão, João Pedro Marciano and Rob Morris (todos do IMPA).

José D. Alvarado (USP)
18/08 (sexta-feira) – 14h – Local: Sala A241 (IME – Bloco A)

Título: A Canonical Ramsey Theorem with List constrains in G(n,p)

Resumo: Neste seminário estudamos uma variante em grafos aleatórios do Teorema de Erdős-Rado (Classical Canonical Ramsey Theorem) sobre a existência de cópias “canônicas” em arestas-colorações arbitrárias de grafos completos. Estimamos a função limiar para a existência de tais cópias quando impomos uma restrição local no número de cores utilizadas.

Esse resultado, em colaboração com Y. Kohayakawa, P. Morris e G. O. Mota, será aplicado num trabalho subsequente (sem restrições locais) onde estimamos o limiar para ciclos pares.

Tássio Naia (USP)
16/06 (sexta-feira) – 14h – Local: Sala A241 (IME – Bloco A)

Título: Jogando “20 perguntas” sobre grafos

Resumo: Dez anos atrás, G.O.H. Katona propôs o problema determinar, para cada grafo $G$, qual o menor tamanho de uma coleção de caminhos $P_1,\ldots,P_t$ em $G$ com a seguinte propriedade: para qualquer par $\{g,h\}$ de arestas distintas de $G$, algum $P_i$ intersecta $\{g,h\}$ em apenas $g$ ou apenas $h$. Dizemos que essa coleção de caminhos separa as arestas de $G$. Discutiremos avanços recentes obtidos para esse problema, confirmando conjecturas propostas por Balogh, Csaba, Martin, and Pluhár e por Falgas-Ravry, Kittipassorn, Korándi, Letzter, e Narayanan.

Este é um trabalho feito em colaboração com Fábio Botler, Marthe Bonamy, François Dross and Jozef Skokan.

Nicolás Sanhueza-Matamala (Universidad de Concepción)
19/05 (sexta-feira) – 14h – Local: Sala A241 (IME – Bloco A)

Título: Cycle decompositions in hypergraphs

Resumo: A cycle decomposition of a hypergraph $G$ is an edge-disjoint collection of cycles which use every edge of $G$. We will present recent results about cycle decompositions in dense uniform hypergraphs, and its relations with the problem of finding hypergraph Euler tours.

Based in joint work with Allan Lo and Simón Piga.

Cristina Gomes Fernandes (USP)
05/05 (sexta-feira) – 14h – Local: Sala A241 (IME – Bloco A)

Título: Empacotamento de árvores balanceadas quase geradoras no $K_{n,n}$
(ou… minha saga com o Lema da Regularidade)

Resumo: Em 1976, Gyárfas conjecturou que qualquer sequência de árvores $T_1,\dots,T_n$, onde $T_i$ tem ordem $i$, pode ser empacotada no $K_n$. Mais recentemente, em 2013, Hollingsworth apresentou uma variante bipartida desta conjectura, que diz que qualquer sequência de árvores $T_{1,1},\dots,T_{n,n}$, onde $T_{i,i}$ tem $i$ vértices em cada lado da sua bipartição, pode ser empacotada no $K_{n,n}$. Tais árvores são chamadas de balanceadas. Existem muitos resultados relacionados à primeira conjectura, mas nem tantos sobre a segunda, mais recente. Neste seminário, daremos uma ideia da prova do seguinte resultado que obtivemos no contexto da segunda conjectura. Informalmente, para $n$ suficientemente grande, sempre é possível empacotar perto de $\sqrt{n}$ árvores quase geradoras no $K_{n,n}$. Formalmente, para todo $\gamma > 0$, existe $n_0$ tal que, para todo $n \geq n_0$, qualquer família de $n^{\frac12-\gamma}$ árvores balanceadas em $2(1-\gamma)n$ vértices pode ser empacotada no $K_{n,n}$.

Este é um trabalho feito em conjunto com Tássio Naia, Giovanne dos Santos e Maya Stein.

Yani Pehova (LSE)
31/03 (sexta-feira) – 14h – Local: Sala A241 (IME – Bloco A)

Título: Transversal factors and spanning trees

Resumo: In this talk we consider a recent transversal, or rainbow, variant of the classical question: for which $d$ do $n$-vertex graphs with minimum degree $d$ always contain a fixed subgraph $H$? We consider a collection of $m$ graphs on the same set of $n$ vertices whose minimum degree is at least $d$, and ask which $d$ guarantee the existence of a fixed ($m$-edge) subgraph $H$ using exactly one edge from each graph in the collection. The obtained copy of $H$ is called a transversal, or a rainbow copy if we view each graph as a different colour. We give asymptotically optimal minimum degree thresholds for the existence of rainbow spanning trees with maximum degree $o(n/\log⁡ n)$ and perfect $F$-tilings in this setting.

This is joint work with Alp Müyesser and Richard Montgomery.

2022

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”.

Leonardo Nagami Coregliano (IAS Princeton)
Data: 25/08 – 14h

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.