Seminars in Extremal, Probabilistic ands Aditive Combinatorics
2023 seminars
- Sebastião Fróes (USP)
- Data e local: 01/12 (sexta-feira) - 14h - Sala A241 (IME – Bloco A)
- Título: O valor assintótico de número de Ramsey 𝑅(4,𝑡)
- 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 𝑅(4,𝑡)
a menos de fatores logarítmicos, assim resolvendo uma conjectura
de Erdős.
- Walner Mendonça dos Santos (USP)
- Data e local: 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 𝑛 vértices pode ser decomposto em 𝑂(𝑛) 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
𝑂(𝑛loglog(𝑛)) 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
𝑂(𝑛log∗(𝑛)) ciclos, onde log∗(𝑛) denota o logaritmo iterado de 𝑛. 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.
- Tássio Naia (USP)
- Data e local: 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 𝐺(𝑛,𝑝)? Nesta
palestra, discutiremos alguns resultados recentes descrevendo uma
classe de árvores orientadas com tamanho (1−𝑜(1))𝑛 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.
- Antônio Kaique Barroso Fernandes (USP)
- Data e local: 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 𝐾𝑛, 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é.