Seminários em Combinatória Extremal, Probabilística e Aditiva

2023

  • 26/05: Tássio Naia (USP)

Local e horário: Sala A241 – 14h

Título: Árvores orientadas contidas em toda orientação do grafo aleatório binomial

Resumo: Quais árvores orientadas estão, com alta probabilidade, contidas em toda orientação do grafo aleatório binomial \(G(n,p)\)? Nesta palestra, discutiremos alguns resultados recentes descrevendo uma classe de árvores orientadas com tamanho
\((1-o(1))n\) que satisfazem a essa propriedade.

Este resultado é fruto de uma colaboração com Gabriel Ferreira Barros, Hiệp Hàn, Yoshiharu Kohayakawa, Matías Pavez-Signé, e Maya Stein.

  • 28/04: Antônio Kaique Barroso Fernandes (USP)

Local e horário: Sala A241 – 14h

Título: Uma prova da conjectura de Lehel

Resumo: Na década de 70, Lehel conjecturou que em toda \(2\)-coloração das arestas de um grafo completo \(K_n\), existe uma partição dos vértices em \(2\) ciclos monocromáticos de cores diferentes, onde o conjunto vazio, um único vértice e arestas são considerados ciclos. Apresentaremos neste seminário uma prova para esta conjectura obtida por Bessy e Thomassé.

  • 16/03: Marcelo Campos (IMPA)

Local e horário: Auditório Imre Simon (CCSL) – 16h

Título: Progresso em um problema de Erdős

Resumo: Nesta palestra apresentarei um progresso recente para um problema antigo e conhecido de Erdős.
Trabalho em colaboração com Simon Griffiths, Robert Morris e Julian Sahasrabudhe

https://arxiv.org/abs/2303.09521

Resumo do manuscrito:

The Ramsey number \(R(k)\) is the minimum \(n\in\mathbb{N}\) such that every red-blue colouring of the edges of the complete graph \(K_n\) on \(n\) vertices contains a monochromatic copy of \(K_k\). We prove that \[R(k) \leq (4-\varepsilon)^k \] for some constant \(\varepsilon > 0\). This is the first exponential improvement over the upper bound of Erdős and Szekeres, proved in 1935.

Seminários em anos anteriores