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

No segundo semestre de 2022, nossas reuniões acontecem no Auditório Imre Simon (IME/USP) às 14h.

2022

  • 16/09: Gabriel Morete de Azevedo (USP) e Jared León (USP)

Título: A conjecture de Kahn e Kalai

Para um conjunto finito \(X\), uma propriedade crescente é uma família \(\mathcal{F} \subseteq 2^X\) tal que se \(W \supseteq U \in \mathcal{F}\) então \(W \in \mathcal{F}\). Em 1987 Bollobás e Thomason provaram que toda propriedade crescente possui um threshold (limiar), isto é, há um valor \(p_c\) tal que a medida binomial em \(\mathcal{F}\) usando \(p = p_c\) é \(1/2\).

Muitos trabalhos foram dedicados a estimar o limiar para diversas propriedades. Em 2006 Kahn e Kalai conjecturaram que esse valor poderia ser estimado utilizando o expectation threshold (um parâmetro simples de calcular) a menos de um erro multiplicativo da ordem de \(\log \vert X \vert\). Em 2022 Park e Pham provaram essa conjectura.

Neste seminário será introduzido o conceito de threshold, expectation threshold, a conjectura e a demonstração de Park e Pham.


  • 02/09: Nathan Benedetto Proença (Universidade de Waterloo)

Título: Homomorfismos de Grafos e Otimização Combinatória

Um homomorfismo de grafo é uma função entre os conjuntos de vértices de dois grafos que mapeia arestas em arestas. Uma \(k\)-coloração de um grafo \(G\) é um homomorfismo de \(G\) para o grafo completo em \(k\) vértices. Nesta apresentação iremos conversar sobre como podemos utilizar otimização para estudar a existência de homomorfismos, discutindo quais os tipos de dualidades que aparecem nesse contexto.


  • 24/06: Antônio Kaique Barroso Fernandes (USP)

Título: Número Size-Ramsey de grafos cúbicos.

O número size-Ramsey de um dado grafo \(H\) é o menor número de arestas tal que existe um grafo \(G\) com essa quantidade de arestas de modo que, para qualquer \(2\)-coloração das arestas de \(G\), existe uma cópia monocromática de \(H\).

Em outubro de 2021 Conlon, Nenadov e Trujic, mostraram que o número size-Ramsey de um grafo cúbico com \(n\) vértices é \(O(n^{8/5})\), melhorando assim a cota anterior de \(O(n^{5/3 +o(1)})\) provada por Kohayakawa, Rödl, Schacht e Szemerédi (2011).

Neste seminário será apresentada a prova exibida por Conlon, Nenadov e Trujic.

– O seminário será online pelo Google Meet: https://meet.google.com/yak-tbwa-rcw


  • 10/06: Fernando Granha Jeronimo (Institute for Advanced Study)

Título: An Invitation to Expander Graphs

Expander graphs are fundamental objects in theoretical computer science and mathematics. They have numerous applications in diverse fields such as algorithm design, complexity theory, coding theory, pseudorandomness, group theory, etc.

The goal of this talk is to provide a brief introduction to these amazing objects and to serve as an invitation for further explorations. We will discuss an elegant construction of expander graphs known as the zig-zag product. Depending on time, we will also
discuss recent developments of “higher-order” zig-zag.

– A palestra será online pelo Google Meet: https://meet.google.com/dsm-kkbt-xvf


  • 30/05: Marcelo Sales (Emory University)

Título: Representação de hipergrafos

Seja \(G\) um \(r\)-grafo com conjunto de vértices \([n]\). Dado um inteiro positivo \(t\), uma família \(\{A_i\}_{i\in [n]} \subseteq 2^{[t]}\) é uma representação de \(G\) se

\(\{i_1,\ldots,i_r\} \in G \quad \Leftrightarrow \quad A_{i_1}\cap A_{i_2}\cap\ldots\cap A_{i_r}\neq \emptyset.\)

Defina \(\Theta(G)\) como o menor inteiro \(t\) admitindo tal representação. Nós discutiremos cotas superiores e inferiores do parâmetro \(\Theta\) para certas famílias de hipergrafos.


  • 27/05: Paulo Matias da Silva Junior (UFABC)

Título: Proper edge colorings of complete graphs without some repeated graphs

Fixado um grafo \(H\), lançamos a questão: qual o menor número de cores \(C\) tal que existe uma coloração própria das arestas do grafo completo \(K_n\) com \(C\) cores que evite duas cópias vértice-disjuntas de \(H\) “isomorfas em cores”? Esse problema foi introduzido por Conlon e Tyomkyn, que o estudaram para algumas classes de grafos. Teremos um breve contato com as ideias deles que tinham foco em resultados assintóticos. Nossa ênfase será tratar de cópias de triângulos com as mesmas cores quando \(n\) é par, conseguindo resultados exatos para valores pequenos de \(n\) e também para infinitos valores de \(n\).


Trabalho em conjunto com Fábio Botler, Lucas Colucci, Guilherme O. Mota, Roberto Parente e Matheus Secco.


  • 29/04 e 06/05: Pedro Santos Mota e Arraes (USP)

Título: Subgrafos Irregulares

Neste seminário, apresentaremos os resultados no artigo “Irregular subgraphs” de Noga Alon e Fan Wei. Os autores propõem duas conjecturas. A primeira afirma que qualquer grafo \(d\)-regular com \(n\) vértices contém um subgrafo gerador tal que, para todo \(k \in [0,d]\) inteiro, o número de vértices de grau \(k\) desvia de \(n/(d+1)\) por no máximo \(2\). A segunda afirma que todo grafo com \(n\) vértices e grau mínimo \(\delta\) contém um subgrafo gerador tal que a quantidade máxima de vértices com o mesmo grau não ultrapassa \(n/(d+1) +2\). Ambas as conjecturas permanecem abertas, porém os autores provam versões assintóticas das mesmas.

Dado um grafo \(H\), seja \(m(H)\) a quantidade máxima de vértices com o mesmo grau em \(H\). Os autores também apresentam limitantes universais mais fracos para \(m(H)\) (uma constante vezes \(n/d\) se \(G\) for \(d\)-regular, e uma constante vezes \(n/\delta\) no caso geral), onde \(H\) é um subgrafo gerador do grafo \(G\). Ademais, eles mostram relações entre essa quantidade e a \(\textit{força de irregularidade}\) do grafo, que é o menor inteiro \(s\) tal que existe \(x\colon E(G) \to [s]\) com \(\sum_{e \ni u} x(e) \neq \sum_{e \ni v} x(e)\) para qualquer par de vértices distintos \(u,v \in V(G)\).

Ref.: https://arxiv.org/abs/2108.02685


  • 08/04: Victor Seixas Souza (Cambridge)

Título: The dimension of the divisibility order

The Dushnik-Miller dimension of a partially-ordered set \(P\) is the smallest \(d\) such that one can embed \(P\) into a product of \(d\) linear orders. We prove that the dimension of the divisibility order on the interval \(\{1, \dots, n\}\) is equal to \((\log n)^2 (\log \log n)^{-\Theta(1)}\) as \(n\) goes to infinity. We will also see similar results when for variant notions of dimension and when the divisibility order taken over various other sets of integers.

Based on joint work with David Lewis and also with Leo Versteegen.


  • 01/04: Lucas Colucci (USP)

Título: Ramsey em grupos: um problema de Caro sobre florestas em \(Z _3\)

Nessa palestra, faremos um breve panorama sobre o problema de Ramsey em grupos, e apresentaremos um esboço da prova obtida recentemente pelo palestrante e co-autores de uma conjectura de Y. Caro sobre número de Ramsey de florestas em \(Z_3\).

Trabalho conjunto com José Alvarado e Roberto Parente.