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

2023

  • 01/12: Sebastião Fróes (USP)

    Local e horário: Sala A241 – 14h

    Título: O valor assintótico de número de Ramsey \(R(4, t)\)

    Resumo: Neste seminário será apresentado um resultado muito recente de S. Mattheus e J. Verstraete, que a partir de uma construção de planos projetivos demonstra a existência de grafos livres de conjuntos independentes grandes ou cliques de tamanho \(4\). Essa construção determina assintoticamente o valor de \(R(4, t)\) a menos de fatores logarítmicos, assim resolvendo uma conjectura de Erdős.
  • 17/11: Walner Mendonça (USP)

    Local e horário: Sala A241 – 14h

    Título: Empacotamento de grafos em ciclos

    Resumo: Uma conjectura sexagenária de Erdős e Gallai afirma que todo grafo com \(n\) vértices pode ser decomposto em \(O(n)\) ciclos, considerando arestas como ciclos de tamanho um. Em 2014, Conlon, Fox e Sudakov apresentaram o primeiro avanço significativo para tal conjectura ao demonstrar que tal decomposição pode ser realizada em \(O(n \log\log(n))\) ciclos, utilizando grafos expansores como base para a construção desses ciclos. Recentemente, Bucić e Montgomery aprimoraram esse resultado mostrando que é possível obter tal decomposição com \(O(n\log^{*}(n))\) ciclos, onde \(\log^{*}(n)\) denota o logaritmo iterado de \(n\). A prova por eles apresentada constitui uma extensão do método de Conlon-Fox-Sudakov, incorporando o uso de expansores sublineares. Neste seminário, exploraremos detalhadamente a prova do primeiro resultado e discutiremos as inovações e técnicas introduzidas no segundo resultado.
  • 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