2021

• 17/12: Olaf Parczyk (Freie Universität Berlin)

Título: The square of a Hamilton cycle in randomly perturbed graphs

We study the model of randomly perturbed dense graphs, which is the union of any \(n\)-vertex graph \(G_\alpha\) with minimum degree \(\alpha n\) and the binomial random graph \(G(n,p)\). For the range \(0 \le \alpha <1\) we are interested in the evolution of the threshold probability \(\hat p(\alpha)\) that determines when \(G_\alpha \cup G(n,p)\) asymptotically almost surely satisfies a given property. In this talk, we focus on the containment of the square of a Hamilton cycle.This is joint work with Julia Böttcher, Amedeo Sgueglia, and Jozef Skokan.

• 10/12: Igor Carboni Oliveira (University of Warwick)

Título: Connections between learning theory and complexity theory

Designing provably correct learning algorithms and showing complexity lower bounds are key challenges in learning theory and complexity theory, respectively. In a recent work (https://arxiv.org/abs/2012.01920), we established a strong connection between these two problems. In other words, it is possible to prove complexity lower bounds by designing new learning algorithms (an upper bound task). In this self-contained presentation, I will provide an introduction to (classical, i.e., non-quantum) learning algorithms, discuss connections between learning and complexity theory, and explain in a simpler setting how to extract hard computational problems from learning algorithms.

• 03/12: Richard Lang (Universität Heidelberg)

Título: Sufficient conditions for Hamilton cycles in dense graphs

A classic theorem of Dirac states that a graph in which every
vertex is connected to half of the other vertices contains a Hamilton
cycle. Over the last decades, this result has been generalized in many
interesting ways. In this talk, I will give an overview of the past
research and then present some new results in this direction for dense
graphs.

• 12/11: Leandro Zatesko (UTFPR)

Título: On the Edge of Edge-colouring

What makes a hard problem hard? In this talk, we approach intriguing facts and state-of-the-art results concerning edge-colouring simple graphs, a problem which many researchers from our latin-american community have been studying. In particular, we present a novel recolouring procedure which extends the well-known Vizing’s recolouring procedure of 1964, leading to results which contribute towards settling the Overfull Conjecture, a main open problem on edge-colouring simple graphs.

• 05/11: Dirk Erhard (UFBA)

Título: How a random walk turns into a swiss cheese

Nesta palestra eu vou falar sobre o passeio aleatório simples condicionado a visitar poucos pontos. A probabilidade de eventos deste tipo foram analisados no início dos anos 2000 por Bolthausen, den Hollander e van den Berg e eles conjecturaram que a estratégia típica para o passeio visitar menos pontos do que tipicamente é seguir a estratégia do queijo suiço, i.e., até o tempo \(n\) o passeio vai ficar numa bola de raio \(n^{1/d}\) e vai deixar buracos de tamanhos aleatórios. Eu vou explicar como é possível relacionar esta ideia ao modelo de percolação introduzido por Sznitman, o modelo de random interlacements. Este é um trabalho em andamento com Julien Poisat (Paris).

• 22/10 e 29/10: Iuri Grangeiro (USP)

Título: Lema local de corte

O lema local de Lovász é um lema de probabilidade que permite achar condições para as quais a baixa probabilidade de eventos ruins é suficiente para garantir que todos os eventos são evitados simultaneamente com probabilidade positiva. Esse lema tem alta aplicabilidade em teoria de grafos, achando condições suficientes para certos padrões serem possíveis, porém, seus limitantes vem sendo superados recentemente por uma versão algorítmica do lema, o método da compressão entrópica. Porém, esse método é consideravelmente mais complexo que o lema original, além de se tratar de um método, não um teorema.

O lema local de corte é uma tentativa de melhorar os limitantes do lema local de Lovász ainda mantendo o formato de lema e a simplicidade de aplicação. Nessa palestra, tentarei esclarecer a relação entre os dois lemas, bem como mostrar uma aplicação do lema local de corte que iguala o melhor resultado conhecido.

• 15/10: Fábio Botler (UFRJ)

Título: A Conjectura de Gallai sobre decomposição de grafos em caminhos

Uma decomposição em caminhos de um grafo \(G\) é um conjunto de caminhos aresta disjuntos em \(G\) que cobrem o conjunto de arestas de \(G\). O menor número de caminhos em uma tal decomposição de \(G\) é chamado de path number de \(G\), e é denotado por \(pn(G)\). Em 1966, Gallai conjecturou que \(pn(G) \leq (n+1)/2\) para todo grafo \(G\) com \(n\) vértices. A Conjectura de Gallai foi verificada para várias classes de grafos, como grafos sem vértices de grau par, grafos com grau máximo \(5\), e grafos planares sem triângulos. Neste seminário discutiremos um pouco mais profundamente as técnicas e ideias envolvidas nestes resultados.

• 08/10: Susanna F. de Rezende (Czech Academy of Sciences)

Título: Clique is hard on average for regular resolution

Resumo: Deciding whether a graph has a \(k\)-clique is one of the most basic computational problems on graphs, and has been extensively studied in computational complexity theory ever since it appeared in Karp’s list of 21 NP-complete problems. In terms of upper bounds, the \(k\)-clique problem can clearly be solved in time roughly \(n^k\) simply by checking if any of the sets of \(k\) vertices forms a clique. The motivating problem behind this work is to determine the exact time complexity of the clique problem when \(k\) is given as a parameter.

In this talk, we will show that for any \(k \leq n^{1/4}\) regular resolution asymptotically almost surely requires length \(n^{\Omega(k)}\) to establish that an Erdős–Rényi random graph with appropriately chosen edge density does not contain a \(k\)-clique. This lower bound is optimal up to the multiplicative constant in the exponent, and also implies unconditional \(n^{\Omega(k)}\)lower bounds on the running time of several state-of-the-art algorithms for finding maximum cliques in graphs. This talk is based on joint work with Albert Atserias, Ilario Bonacina, Massimo Lauria, Jakob Nordström and Alexander Razborov.

• 01/10: Paulo Matias da Silva Junior (UFABC)

Título: Cobertura de grafos via árvores monocromáticas e resultados tipo Helly para hipergrafos

Resumo: Quantos caminhos, ciclos ou árvores monocromáticos são necessários para cobrir todos os vértices de uma dada \(r\)-coloração de arestas de um grafo \(G\)? Este problema já tem sido estudado por 50 anos e, neste seminário, apresentaremos resultados recentes de cobertura de árvores para o grafo aleatório, mostrando uma conexão desse problema geral para hipergrafos e propriedades tipo Helly. Baseado no trabalho de Bucić, Korándi e Sudakov.

• 24/09: Afonso Ali Gonçalves (UNICAMP)

Título: Árvores geradoras independentes e aresta-independentes

Resumo: Sejam \(T_1\) e \(T_2\) duas árvores geradoras de \(G\) enraizadas em qualquer vértice \(r \in V(G)\). Dizemos que as duas árvores \(T_1\) e \(T_2\) são independentes se para todo vértice \(x \neq r \in V(G)\), os caminhos de \(r\) a \(x\) em \(T_1\) e \(T_2\) são internamente disjuntos. Analogamente, dizemos que \(T_1\) e \(T_2\) são aresta-independentes se os caminhos de \(r\) a \(x\) em \(T_1\) e \(T_2\) são aresta-disjuntos. Ambos conceitos foram propostos em 1988 por Itai e Rodeh como uma abordagem para garantir a estabilidade em redes de comunicações a partir do uso de múltiplas árvores geradoras e independentes. Os autores conjecturaram que em todo grafo \(k\)-conexo existem \(k\) árvores geradoras independentes e demonstraram o caso \(k=2\). Além disso, conjecturaram que em todo grafo \(k\)-aresta-conexo existem \(k\) árvores geradoras aresta-independentes. As conjecturas ficaram conhecidas como as Conjecturas das Árvores (Aresta-)Independentes e ambas permanecem abertas para os casos \(k \geq 5\). Neste seminário, abordaremos os resultados acerca de ambas conjecturas e nos aprofundaremos na demonstração do caso \(k=4\) da Conjectura das Árvores Geradoras Aresta-Independentes, demonstrado por Hoyer e Thomas em 2018.

• 17/09: Lucas Colucci (USP) – Parte 2

Título: Teoria de Ramsey em grupos

Resumo: Nestas palestras, faremos um breve panorama sobre resultados da Teoria de Ramsey em grupos. O tipo de problema estudado é o seguinte: dado um grupo \(G\) (tipicamente \(Z_m\) para algum \(m\)) e um grafo \(H\), definimos \(R(H,G)\) como sendo o menor inteiro positivo \(t\) tal que toda coloração das arestas do grafo completo \(K_t\) usando elementos de \(G\) como cores possui um subgrafo isomorfo a \(H\) tal que a soma das ‘cores’ das arestas de \(H\) é \(0\) (em \(G\)). Para quais pares \((G,H)\) esse número existe, e, nesse caso, quão precisamente podemos estimar seu valor?

• 03/09: Lucas Colucci (USP) – Parte 1

Título: Teoria de Ramsey em grupos

Resumo: Nestas palestras, faremos um breve panorama sobre resultados da Teoria de Ramsey em grupos. O tipo de problema estudado é o seguinte: dado um grupo \(G\) (tipicamente \(Z_m\) para algum \(m\)) e um grafo \(H\), definimos \(R(H,G)\) como sendo o menor inteiro positivo \(t\) tal que toda coloração das arestas do grafo completo \(K_t\) usando elementos de \(G\) como cores possui um subgrafo isomorfo a \(H\) tal que a soma das ‘cores’ das arestas de \(H\) é \(0\) (em \(G\)). Para quais pares \((G,H)\) esse número existe, e, nesse caso, quão precisamente podemos estimar seu valor?

• 27/08: Carlos Hoppen (UFRGS)

Título: Decomposições de grafos e autovalores

Resumo: Decomposições de grafos e representações de classes de grafos têm sido exploradas em algoritmos de localização de autovalores, algoritmos cuja entrada consiste em um grafo G e um intervalo I, e cuja saída é o número de autovalores de G em I, contando multiplicidades. Nessa palestra, discutirei avanços nessa direção, particularmente avanços baseados em decomposições em árvore (tree decompositions).

A palestra inclui resultados em co-autoria com Martin Fürer (Pennsylvania State University), David Jacobs (Clemson University) e Vilmar Trevisan (UFRGS).

Referências

[1] Fürer, H., and Trevisan, Efficient diagonalization of Symmetric Matrices
Associated with Graphs of Small Treewidth, 

https://drops.dagstuhl.de/opus/volltexte/2020/12459/pdf/LIPIcs-ICALP-2020-52.pdf

[2] Fürer, H., Jacobs, and Trevisan, Eigenvalue location in graphs of small clique-width

https://www.sciencedirect.com/science/article/abs/pii/S0024379518304506

[3] Jacobs and Trevisan, Locating the eigenvalues of trees

https://www.sciencedirect.com/science/article/pii/S0024379510004143

• 30/07: Tássio Naia (USP) – Continuação

Título: Número cromático de subgrafos acíclicos de torneios

Resumo: Qual é o maior inteiro k=k(n) tal que toda orientação do grafo
completo com n vértices contém necessariamente um subdigrafo
acíclico com número cromático k?

Fox, Kwan e Sudakov [1] obtiveram a cota inferior n^{5/9 -o(1)}
e a cota superior n^{3/4 + o(1)} para k. Apresentaremos a
demontração da cota inferior. As melhores cotas conhecidas haviam
sido obtidas por Nassar and Yuster [2].

[1]: https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/blms.12446
https://arxiv.org/abs/1912.07722v1

[2]: https://www.sciencedirect.com/science/article/abs/pii/S0195669818301331
https://arxiv.org/abs/1811.05734

• 23/07: Tássio Naia (USP)

Título: Número cromático de subgrafos acíclicos de torneios

Resumo: Qual é o maior inteiro k=k(n) tal que toda orientação do grafo
completo com n vértices contém necessariamente um subdigrafo
acíclico com número cromático k?

Fox, Kwan e Sudakov [1] obtiveram a cota inferior n^{5/9 -o(1)}
e a cota superior n^{3/4 + o(1)} para k. Apresentaremos a
demontração da cota inferior. As melhores cotas conhecidas haviam
sido obtidas por Nassar and Yuster [2].

[1]: https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/blms.12446
https://arxiv.org/abs/1912.07722v1

[2]: https://www.sciencedirect.com/science/article/abs/pii/S0195669818301331
https://arxiv.org/abs/1811.05734

• 16/07: Jared León (USP)

Título: A proof of the Győri-Lovász theorem for k-splitting k-connected graphs

Resumo: The Győri-Lovász theorem states that, given a k-connected graph G of order n, a sequence n_i of k positive integers that sum up to n, and a sequence of k distinct vertices v_i of G, it is possible to find k disjoint subgraphs G_i of G such that G_i has order n_iand contains vertex v_i.

L. Lovász and E. Győri independently proved this theorem at about the same time. Lovász’sproof uses topological methods, whereas Győri’s proof uses classic graph theory only. Later,A. Hoyer and R. Thomas presented a self-contained proof of the theorem using ideas ofGyőri’s proof. In this seminar, I will present Hoyer and Thomas’ proof of the theorem.

References:
[1] E. Győr, On division of graphs to connected subgraphs, Colloq, Math. Soc. JanosBolyai, 18, Combinatorics, Keszthely (Hungary) (1976), 485-494.
[2] L. Lovász, A homology theory for spanning trees of a graph, Acta Math. Acad. Sci.Hungaricae 30 (1977), 241-251
[3] A. Hoyer, R. Thomas, The Gyori-Lovasz theorem, arXiv preprint arXiv:1605.01474 (2016).

• 02/07: Fernando Mário de Oliveira Filho (TU Delft)

Título: O número theta de Lovász para hipergrafos e cotas para densidade
de conjuntos que evitam simplexos

Resumo: O número theta de Lovász é um limitante superior para o número de
independência de um grafo.  Neste seminário, vou mostrar uma forma de estender esse limitante para hipergrafos uniformes na esfera e no espaço euclidiano.

Uma análise do limitante resultante fornece cotas superiores para a densidade de conjuntos no R^n que não contêm os vértices de um k-simplexo regular de lado unitário.  Como resultado, é possível provar que a densidade de um tal conjunto no R^n decai exponencialmente com a dimensão do espaço.  Outras provas desse decaimento exponencial foram fornecidas por Frankl e Rödl, usando o método de álgebra linear, e
Naslund, usando o recente método de slice rank de tensores.  As cotas que se obtêm a partir da extensão do número theta de Lovász são melhores que as fornecidas por ambos esses métodos.

(Trabalho em conjunto com Davi Castro-Silva, Lucas Slot e Frank Vallentin.)

• 25/06: Gabriel Barros (USP)

Título: Subgrafos sem C_4 de grau médio grande

Resumo: Uma conjectura de Thomassen, de 1983, afirma que, dados inteiros t e g, existe f(t,g) tal que todo grafo com grau médio pelo menos f(t,g) contém um subgrafo com grau médio pelo menos t e sem circuitos de comprimento no máximo g-1. Kühn e Osthus, em 2004, provaram a existência de f(t,6), mostrando que é suficiente que f(t,6) = exp(exp(c t^3)) para alguma constante c. Nesta palestra, falarei sobre o resultado de Montgomery, Pokrovskiy e Sudakov, publicado no arXiv em 2020, que mostra que basta que f(t,6) = exp(c t^2 log t). Assim como a prova de Kühn e Osthus, tal prova se reduz a encontrar um subgrafo sem C_4 de grau médio pelo menos t em um grafo bipartido de grau médio suficientemente grande.

• 18/06: Patrick Morris (Freie Universität Berlin)

Título: Triangle factors in pseudorandom graphs

Resumo: An (n, d, λ)-graph is an n vertex, d-regular graph with second eigenvalue in absolute value λ. When λ is small compared to d, such graphs have pseudo-random properties. A fundamental question in the study of pseudorandom graphs is to find conditions on the parameters that guarantee the existence of a certain subgraph. A celebrated construction due to Alon gives a triangle-free (n, d, λ)-graph with d = Θ(n^2/3) and λ = Θ(d^2/n). This construction is optimal as having λ = o(d^2/n) guarantees the existence of a triangle in a (n, d, λ)-graph. Krivelevich, Sudakov and Szabó (2004) conjectured that if n ∈ 3N and λ = o(d^2/n) then an (n, d, λ)-graph G in fact contains a triangle factor: vertex disjoint triangles covering the whole vertex set. 

In this talk, we discuss a solution to the conjecture of Krivelevich, Sudakov and Szabó. The result can be seen as a clear distinction between pseudorandom graphs and random graphs, showing that essentially the same pseudorandom condition that ensures a triangle in a graph actually guarantees a triangle factor. In fact, even more is true: as a corollary to this result and a result of Han, Kohayakawa, Person and the author, we can conclude that the same condition actually guarantees that such a graph G contains every graph on n vertices with maximum degree at most 2.

• 11/06: Fabrício Benevides (UFC)

Título: On Heilbronn triangle-type problems in higher dimensions

Resumo: The Heilbronn triangle problem is a classical geometrical problem that asks for a placement of n points in the unit-square [0,1]^2, that maximizes the smallest area of a triangle formed by those points. This problem has natural generalizations to higher dimensions. For integers k, d > 1 and a set P of n points in [0,1]^d, let s be the minimun of (k-1) and d; and let V(k, d, P) be the minimum s-dimensional volume of the convex hull of k points in P. Here, instead of considering the supremum of V(k, d, P), we consider its average value, avrgDelta(k, d, n), when the n points in P are chosen independently and uniformly at random in [0,1]^d. We prove that avrgDelta(k, d, n) is of order n to the power of (-k / {1 + |d-k+1| } ), for every fixed k, d > .

Trabalho em conjunto com C. Hoppen, H. Lefmann e K. Odermann.

• 04/06: Roberto Parente (USP / UFBA)

Título: Arborescências em grafos aleatórios – Parte II

Resumo: Uma arborescência é um digrafo com n vértices e n−1 arcos tais que existe um vértice (raiz) tal que pode alcançar qualquer outro vértice através dos caminhos direcionados.  Nesta segunda parte apresentaremos um resultado de hitting-time em modelos de processos de digrafos aleatórios apresentado no LAGOS 2021 e apresentaremos algumas ideias e caminhos para generalizações.

Trabalho em conjunto com Collares, Kohayakawa, Martins e Souza.

• 28/05: Roberto Parente (USP / UFBA)

Título: Arborescências em grafos aleatórios – Parte I

Resumo: Uma arborescência é um digrafo com n vértices e n−1 arcos tais que existe um vértice (raiz) que pode alcançar qualquer outro vértice através dos caminhos direcionados. Nessas duas apresentações discutiremos resultados sobre o hitting-time e packing de arborescência em digrafos aleatórios e processos de digrafos aleatórios. Na primeira parte apresentaremos o resultado inicial de Hoppen-Parente-Sato (SIDMA’17) que afirma sobre empacotamento de arborescências em Dnp e introduziremos os modelos de processos de digrafos aleatórios e o resultado de Collares-Kohayakawa-Martins-Parente-Souza (LAGOS 2021).

• 14/05: Lucas Colucci (USP)

Título: Coloração de arestas módulo k

Resumo: Nesse seminário, falaremos sobre colorações módulo k, isso é, colorações de arestas de grafos tais que o número de arestas de cada cor incidente a cada vértice é congruente a 1 mod k. Mostraremos um resultado recente de que o número máximo de cores necessários para essa tal coloração é uma função linear de k, respondendo afirmativamente uma pergunta de Scott, o que determina corretamente esse número a menos de uma constante multiplicativa. Também mencionaremos alguns resultados sobre grafos aleatórios e problemas em aberto.

Trabalho em conjunto com Fábio Botler e Yoshiharu Kohayakawa.

• 07/05: Lucas Colucci (USP)

Título: Coloração L(2,1) de grafos e generalizações

Resumo: Nesse seminário, faremos um panorama sobre coloração L(2,1) de grafos e várias de suas generalizações, com foco em problemas menos estudados e possíveis novas direções de pesquisa.

• 30/04: José Alvarado (USP)

Título: New Short Proofs to Some Stability Theorems (Xizhi Liu — 2019)

Resumo: Neste artigo o autor apresenta provas curtas para dois tipos de Problemas de Turán em Hipergrafos, abarcando resultados exatos e de estabilidade em ambos. O primeiro dos problemas que veremos foi estudado inicialmente por Mubayi, e o segundo foi estudado por Bollobás e posteriormente por Keevash e Mubayi. Além disso, o resultado apresentado neste artigo é mais efetivo, no sentido que mostra uma dependência linear entre os parâmetros envolvidos nos resultados de estabilidade.

• 23/04: Marcelo Campos (IMPA)

Título: Contando orientações de G(n,p) sem C_r direcionado

Resumo: Dados um grafo G e um grafo orientado \vec{H} podemos perguntar quantas orientações de G não contém \vec{H} como subgrafo orientado? Nesse seminário vou responder essa pergunta quando \vec{H} é um ciclo C_r direcionado e G=G(n,p). Em particular vou mostrar um argumento de Collares, Kohayakawa, Morris e Mota que funciona para C_3 direcionado e uma generalização para C_r direcionado, com r > 3.

Este é um trabalho conjunto com Maurício Collares e Guilherme Mota.

• 16/04: Walner Mendonça (IMPA)

Título: Tiling edge-coloured graphs with few monochromatic bounded-degree graphs

Resumo: Gerencsér e Gyárfás provaram em 1967 que para qualquer 2-coloração das arestas de K_n, é possível particionar V(K_n) em dois caminhos monocromáticos. Tal resultado, cuja a prova é bastante simples, motivou inúmeros outros problemas desafiantes os quais têm sido objetos de extensa pesquisa em combinatória extremal nos últimos anos. Por exemplo, Erdős, Gyárfás e Pyber conjecturaram em 1991 que para toda r-coloração de K_n existem r caminhos monocromáticos particionando V(K_n). Podemos também encontrar na literatura outras versões do problema onde ao invés de obtermos particionamento por caminhos, foca-se em obter particionamento por árvores, ciclos ou até mesmo potência de ciclos.

Grinshpun e Sárközy estudaram uma versão mais geral do problema onde interessa-se em particionar V(K_n) em subgrafos monocromáticos de grau limitado. Eles provaram que para toda sequência de grafos S = (F_i, i \in \mathbb{N}) com |F_i| = i e \Delta(F_i) \leq D, o seguinte vale: para qualquer 2-coloração das arestas de K_n é possível particionar V(K_n) em no máximo 2^{O(D \log D)} cópias monocromáticas de grafos da sequência S. Eles conjecturaram que para r-colorações, também deve ser verdade que é possível particionar V(K_n) em uma quantidade exponencial de cópias monocromáticas de grafos da sequência S. Mais precisamente, a conjectura deles afirma que para todo inteiro positivo r, existe uma constante C=C(r) para o qual o seguinte vale: para qualquer r-coloração das arestas de K_n, é possível particionar V(K_n) em no máximo 2^{D^C} cópias monocromáticas de grafos da sequência S. Neste trabalho apresentamos o primeiro progresso na conjectura de Grinshpun e Sárközy estabelecendo um limitante triplamente exponencial.

Este é um trabalho conjunto com Jan Corsten (LSE, UK).