2022
- 16/12: Letícia Mattos (Freie Universität Berlin)
Local: sala 249-A.
Título: Bounds For Essential Covers Of The Cube
Resumo: An essential cover of the vertices of the \(n\)-cube \(\{-1,1\}^n\) by hyperplanes is a minimal covering where no hyperplane is redundant and every variable appears in the equation of at least one hyperplane. Linial and Radhakrishnan gave a construction of an essential cover with \(n/2+1\) hyperplanes and showed that \(\sqrt{n}\ \) hyperplanes are required. Recently, Yehuda and Yehudayoff improved the lower bound by showing that any essential cover of the \(n\)-cube contains at least \(n^{0.52}\) hyperplanes. In this talk, we show that \(n^{5/9}\) hyperplanes are needed. This is based on a joint work with Araujo and Balogh.
- 25/11: Pedro Araújo (The Czech Academy of Sciences)
Horário: 13h – Online – Assistiremos na sala 249-A.
Título: Número de Ramsey de ciclos em grafos aleatórios
Seja \(R(C_n)\) o número de Ramsey do ciclo com n vértices. Nós provamos que, para alguma constante \(C>0\), com alta probabilidade toda \(2\)-coloração das arestas de \(G(N,p)\) contém uma cópia monocromática de \(C_n\), contanto que \(N> R(C_n)\) e \(p>C/N\). Esse resultado é o melhor possível exceto pelo valor de \(C\) e melhora resultados prévios de Letzter e de Krivelevich, Kronenberg e Mond.
- 18/11: Lucas Colucci (USP)
Horário: 11h – Sala A259
Título: Problemas e resultados sobre torneios
Nesta palestra faremos um panorama breve sobre alguns problemas e resultados sobre estruturas em torneios, incluindo resultados recentes e problemas em aberto. Parcialmente baseado em trabalho conjunto com Tássio Naia.
- 04/11: Marcelo Campos (IMPA)
Título: Cotas inferiores para números size-Ramsey
O número size-ramsey \(\hat{r}(H)\) de um grafo \(H\) é o menor \(m\) tal que existe um grafo \(G\) com \(m\) arestas e toda \(2\)-coloração das arestas de \(G\) contém uma cópia monocromática de \(H\).
Nesse seminário vou mostrar uma construção de Tikhomirov de um grafo \(3\)-regular \(H\) com \(n\) vértices e \(\hat{r}(H)\geq \exp(c\sqrt{\log n}) n\).
- 30/09: Jared León (USP)
Título: A conjectura de Kahn e Kalai – Parte II
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.
- 28/09: Marcelo Campos (IMPA)
Título: Singularidade de matrizes aleatórias simétricas
Seja \(A\) uniformemente aleatória no conjunto de todas as matrizes \(n\times n\) simétricas com entradas em \(\{-1,1\}\). Falarei sobre um resultado em que mostramos que \(\mathbb{P}(\det(A) = 0) \leq e^{-cn}\), para \(c>0\) uma constante absoluta.
Trabalho em colaboração com Matthew Jenssen, Marcus Michelen e Julian Sahasrabudhe.
- 30/09: Gabriel Morete de Azevedo (USP)
Título: A conjectura de Kahn e Kalai – Parte I
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.
- Seminários em anos anteriores