2024
- Joseph Hyde (University of Victoria)
7/6 (sexta-feira) – 15h30 – Local: Auditório do NUMEC
Título: Thresholds for random Ramsey problems
Resumo: The study of Ramsey properties of the binomial random graph \(G_{n,p}\) was initiated in the 80s by Frankl & Rödl and Łuczak, Ruciński & Voigt. In this area we are often interested in establishing what function \(f(n)\) governs \(G_{n,p}\) having a particular Ramsey-like property \(P\) or not, i.e. when \(p\) is sufficiently larger than \(f(n)\) then \(G_{n,p}\) a.a.s. has \(P\) and when \(p\) is sufficiently smaller than \(f(n)\) then \(G_{n,p}\) a.a.s. does not have \(P\) (the former we call a 1-statement, the latter a 0-statement). We present recent results on this topic from two different papers. In the first, we almost completely resolve an outstanding conjecture of Kohayakawa and Kreuter on asymmetric Ramsey properties. In particular, we reduce the 0-statement to a necessary colouring problem which we solve for almost all pairs of graphs. Joint work with Candy Bowtell and Robert Hancock.
In the second, we prove similar results concerning so-called anti- and constrained-Ramsey properties. In particular, we (essentially) completely resolve the outstanding parts of the problem of determining the threshold function for the constrained-Ramsey property, and we reduce the anti-Ramsey problem to a colouring problem which we solve for a specific collection of graphs. Joint work with Natalie Behague, Robert Hancock, Shoham Letzter and Natasha Morrison.
We finish with a number of open problems. - Théo Borém Fabris (USP)
24/5 (sexta-feira) – 15h30 – Local: Auditório Jacy Monteiro (Bloco B)
Título: Circuitos monótonos e o problema do clique
Resumo: Neste seminário será apresentada uma prova combinatória de uma cota inferior para o tamanho de circuitos monótonos que computam a função Booleana \(\text{Clique}_{n,3}\). A apresentação será baseada na prova de Simon e Tsai (2000). A cota inferior obtida por eles é ligeiramente melhor que um resultado obtido por Razborov (1985), mas eles não utilizaram explicitamente o método das aproximações combinado com teoremas sobre sunflowers, que são as técnicas mais usuais.
Seminários – Problemas de separação por caminhos
Teremos alguns seminários sobre resultados recentes acerca do problema de separação por caminhos. Serão apresentados os resultados descritos nos seguintes trabalhos:
– https://arxiv.org/abs/2301.08707
– https://arxiv.org/abs/2312.14879
– https://arxiv.org/abs/2403.08210
- George Kontogeorgiou (University of Chile)
3/5 (sexta-feira) – 14h – Local: Auditório Jacy Monteiro (Bloco B)
Título: Small weakly separating path systems for complete graphs
Resumo: Let G be a graph and let P be a set of paths of G. We say that P
weakly separates G if for every pair of edges of G there exists a path
in P that contains exactly one of them. It is a well-known problem to
determine the size of the smallest weakly separating path system of a
given graph on n vertices. Around a decade ago, Falgas-Ravry,
Kittipassorn, Korandi, Letzter and Narayanan conjectured an upper
bound of O(n) paths. This was proved last year by Bonamy, Botler,
Dross, Naia and Skokan, who further conjectured an upper bound of
(1+o(1))n paths.
Some authors have considered the restriction of this problem to
complete graphs. It is known that a weakly separating path system for
a complete graph on n vertices must contain at least n-1 paths. Recently, Fernandes, Mota and Sanhueza-Matamala proved that (1+o(1))n paths suffice.
In recent work with Maya Stein, we proved that every complete graph on
n vertices has a weakly separating path system of n+2 paths. I will
provide a brief view of the history of the problem and a proof sketch.
- Francisco Calvillo Marmaneu (Universidade Pompeu Fabra)
3/5 (sexta-feira) – 15h – Local: Auditório Jacy Monteiro (Bloco B)
Título: Archeology in random graphs: root-finding methods in large growing networks
Resumo: With the ubiquitous presence of networks in many areas of science and technology, numerous new challenges have gained importance in the statistical analysis of networks. One such area, termed network archaeology (Navlakha and Kingsford, 2011), studies problems related to unveiling the past of dynamically growing networks based on present-day observations. In the models studied in this area, network vertices arrive one by one, and a new vertex attaches to one or more existing vertices by an edge according to some simple probabilistic rule (this is the case, for example, for the uniform random recursive graph, or the preferential attachment model).
This presentation delves into one of the simplest problems of network archaeology: root-finding. It consists of estimating the first vertex of a randomly growing network based on observing the unlabeled network at a much later point in time. We will discuss several root-finding algorithms capable of selecting a small number of nodes—regardless of the graph’s size—such that the root vertex is among them with high probability.
- Rafael Colares (Université Clermont Auvergne)
22/4 (segunda-feira) – 16h – Local: Auditório Antonio Gilioli (Bloco A)
Título: A branch-and-cut algorithm for the availability-aware VNF placement problem in virtualized networks
Resumo: In the context of telecommunication virtualized networks, a Service Function Chain (SFC) is an origin-destination traffic demand having some specific service requirements. These requirements are expressed as an ordered set of Network Functions (NF) that must be visited along the SFCs route. Within virtualized networks, the failure of a single node where a network function is hosted causes the crash of the whole SFC. Our work addresses the problem of optimally placing Virtual Network Functions throughout a 5G network so that a given set of Service Function Chains can achieve high levels of end-to-end availability. We tackle this problem from a combinatorial perspective and propose a probabilistic approach to evaluate the real end-to-end availability of a service. This generates a non-linear character to the problem which is then linearized to derive an original integer programming formulation for it. We also introduce new families of valid inequalities reinforcing the formulation. Based on these inequalities, a branch-and-cut algorithm is proposed.
- Guilherme Mota (USP)
19/4 (sexta-feira) – 14h – Local: A249 (Bloco A)
Título: Sistemas de separação por caminhos em grafos completos
Resumo: Mostraremos que em qualquer grafo completo com \(n\) vértices há uma coleção \(P\) de \((1 + o(1))n\) caminhos que separa fortemente qualquer par \(\{e,f\}\) de arestas distintas, isto é, há um caminho em \(P\) que contém a aresta \(e\), mas não contém a aresta \(f\), e outro caminho em \(P\) que contém a aresta \(f\) mas não contém a aresta \(e\). Além disso, para certas classes de grafos \(\alpha n\)-regulares com \(n\) vértices, encontramos uma coleção de \( (\sqrt{3\alpha + 1} – 1 + o(1))n\) caminhos que separa fortemente qualquer par de arestas. Ambos os resultados são os melhores possíveis a menos do termo \(o(1)\).
Trabalho em conjunto com Cristina Gomes Fernandes e Nicolás Sanhueza-Matamala.
- Fábio Botler (USP)
12/4 (sexta-feira) – 14h – Local: Auditório Jacy Monteiro (Bloco A)
Título: Separating the edges of a graph by a linear number of paths
Resumo: Recently, Letzter proved that any graph of order \(n\) contains a collection of \(O(n\log^{\star} n)\) paths with the following property: for all distinct edges \(e\) and \(f\) there exists a path \(\mathcal{P}\) in which contains \(e\) but not \(f\). We improve this upper bound to \(19n\), thus answering a question of G.O.H. Katona and confirming a conjecture independently posed by Balogh, Csaba, Martin, and Pluhár and by Falgas-Ravry, Kittipassorn, Korándi, Letzter, and Narayanan. Our proof is elementary and self-contained.
Joint work with Marthe Bonamy, François Dross, Tássio Naia and Jozef Skokan
- Vinicius Fernandes dos Santos (UFMG)
13/3 (quarta-feira) – 14h – Local: Auditório Imre Simon (IME – CCSL)
Título: Jogos, Quebra-Cabeças e Complexidade Computacional
Resumo: Muitos jogos e quebra-cabeças atraem o interesse de pessoas em busca de desafios intelectuais. De certa forma, a dificuldade de uma atividade ajuda a torná-la instigante: um quebra-cabeça muito simples rapidamente se torna desinteressante. Frequentemente tal dificuldade pode ser formalizada, permitindo demonstrar que tais jogos também são difíceis, em diferentes níveis, até mesmo para modelos computacionais.
O estudo da dificuldade de jogos acompanhou os avanços da complexidade computacional, não só utilizando as ferramentas já existentes para a determinação da dificuldade de certos jogos, mas também motivando o desenvolvimento e formalização de novas ideias e modelos.
Nesta palestra discutiremos jogos conhecidos e como diferentes jogos, alguns conhecidos e outros artificiais, se posicionam em diversas classes de complexidade, não apenas nas famosas classes P e NP, mas também em classes mais gerais, como PSPACE e EXP.
- Marcelo Campos (Universidade de Cambridge)
8/3 (sexta-feira) – 14h – Local: Sala B03 (IME – Bloco B)
Título: A new lower bound for sphere packing
Resumo: We show there exists a packing of identical spheres in \(\mathbb{R}_d\) with density at least \[(1−o(1))\frac{d\log d}{2d+1}\] as \(d\to\infty\). This improves upon previous bounds for general \(d\) by a factor of order \(\log d\) and is the first asymptotically growing improvement to Rogers’ bound from 1947.
Joint work with Matthew Jenssen, Marcus Michelen, Julian Sahasrabudhe.
2023
- Marcelo Campos (Universidade de Cambridge)
15/12 (sexta-feira) – 15h – Local: Auditório Jacy Monteiro (IME – Bloco B)
Título: Número de independência de grafos de Cayley mais esparsos
Resumo: Dado \(A \subseteq \mathbb{Z}n\) \(p\)-aleatório, o grafo de Cayley aleatório \(\Gamma_p\) é definido com tendo vértices \(\mathbb{Z}_n\) e uma aresta entre \(x, y \in \mathbb{Z}_n\) se \(x + y \in A\). Para \(p=1/2\), Green e Morris mostraram que o número de independência de \(\Gamma{1/2}\) é assintoticamente igual a \(\alpha(G(n, 1/2))\), com alta probabilidade. Neste seminário vou mostrar que o número de independência de \(\Gamma_p\) se iguala ao de \(G(n,p)\) para \(p \geq (\log n)^{-1/80}\).
Trabalho em conjunto com Lucas Aragão, Gabriel Dahia e João Pedro Marciano.
- Nathan Benedetto Proença (Universidade de Waterloo)
22/09 (sexta-feira) – 14h – Local: Sala A241 (IME – Bloco A)
Título: The Goemans and Williamson Algorithm Extended to the Weighted Fractional Cut-Covering Problem
Resumo: A fractional cut cover is a weighted collection of cuts in a graph covering each edge at least once. The fractional cut-covering problem is to compute, given an input graph, the smallest (total) weight of a fractional cut cover. We study a generalization of this problem, where one can parametrize how many times each edge must be covered. This generalization is tied to the maximum cut problem via convex duality. This relationship affords a primal-dual extension of the celebrated work of Goemans and Williamson. We develop algorithms producing not only approximately optimal fractional cut covers, but also simultaneously certifying optimality of fractional cut-covering and maximum cut instances.
This is joint work with Marcel K. de Carli Silva (USP), Cristiane Sato (UFABC), and Levent Tunçel (University of Waterloo).
- Walner Mendonça (USP)
01/09 (sexta-feira) – 14h – Local: Sala A241 (IME – Bloco A)
Título: Ramsey-bondade em grafos densos
Resumo: Dizemos que um grafo \(G\) é Ramsey para o par de grafos \((F,H)\), se em toda coloração das arestas de \(G\) com as cores vermelho e azul, existe uma cópia vermelha de \(F\) ou uma cópia azul de \(H\). Chvátal mostrou que o grafo completo \(K_n\) é Ramsey para o par \((K_r,P_t)\), para \(n \geq (r-1)(t-1) + 1\). Neste seminário, generalizaremos o teorema de Chvátal mostrando que para qualquer grafo \(G\) com \(n=(r-1)(t-1) + 1\) vértices e \(\delta(G)\geq n – t/2\), temos que \(G\) é Ramsey para \((K_r,P_t)\). Com este resultado, iniciamos o estudo de Ramsey-bondade em grafos densos.
Trabalho em conjunto com Lucas Aragão, João Pedro Marciano and Rob Morris (todos do IMPA).
- José D. Alvarado (USP)
18/08 (sexta-feira) – 14h – Local: Sala A241 (IME – Bloco A)
Título: A Canonical Ramsey Theorem with List constrains in G(n,p)
Resumo: Neste seminário estudamos uma variante em grafos aleatórios do Teorema de Erdős-Rado (Classical Canonical Ramsey Theorem) sobre a existência de cópias “canônicas” em arestas-colorações arbitrárias de grafos completos. Estimamos a função limiar para a existência de tais cópias quando impomos uma restrição local no número de cores utilizadas.
Esse resultado, em colaboração com Y. Kohayakawa, P. Morris e G. O. Mota, será aplicado num trabalho subsequente (sem restrições locais) onde estimamos o limiar para ciclos pares.
- Tássio Naia (USP)
16/06 (sexta-feira) – 14h – Local: Sala A241 (IME – Bloco A)
Título: Jogando “20 perguntas” sobre grafos
Resumo: Dez anos atrás, G.O.H. Katona propôs o problema determinar, para cada grafo \(G\), qual o menor tamanho de uma coleção de caminhos \(P_1,\ldots,P_t\) em \(G\) com a seguinte propriedade: para qualquer par \(\{g,h\}\) de arestas distintas de \(G\), algum \(P_i\) intersecta \(\{g,h\}\) em apenas \(g\) ou apenas \(h\). Dizemos que essa coleção de caminhos separa as arestas de \(G\). Discutiremos avanços recentes obtidos para esse problema, confirmando conjecturas propostas por Balogh, Csaba, Martin, and Pluhár e por Falgas-Ravry, Kittipassorn, Korándi, Letzter, e Narayanan.
Este é um trabalho feito em colaboração com Fábio Botler, Marthe Bonamy, François Dross and Jozef Skokan.
- Nicolás Sanhueza-Matamala (Universidad de Concepción)
19/05 (sexta-feira) – 14h – Local: Sala A241 (IME – Bloco A)
Título: Cycle decompositions in hypergraphs
Resumo: A cycle decomposition of a hypergraph \(G\) is an edge-disjoint collection of cycles which use every edge of \(G\). We will present recent results about cycle decompositions in dense uniform hypergraphs, and its relations with the problem of finding hypergraph Euler tours.
Based in joint work with Allan Lo and Simón Piga.
- Cristina Gomes Fernandes (USP)
05/05 (sexta-feira) – 14h – Local: Sala A241 (IME – Bloco A)
Título: Empacotamento de árvores balanceadas quase geradoras no \(K_{n,n}\)
(ou… minha saga com o Lema da Regularidade)
Resumo: Em 1976, Gyárfas conjecturou que qualquer sequência de árvores \(T_1,\dots,T_n\), onde \(T_i\) tem ordem \(i\), pode ser empacotada no \(K_n\). Mais recentemente, em 2013, Hollingsworth apresentou uma variante bipartida desta conjectura, que diz que qualquer sequência de árvores \(T_{1,1},\dots,T_{n,n}\), onde \(T_{i,i}\) tem \(i\) vértices em cada lado da sua bipartição, pode ser empacotada no \(K_{n,n}\). Tais árvores são chamadas de balanceadas. Existem muitos resultados relacionados à primeira conjectura, mas nem tantos sobre a segunda, mais recente. Neste seminário, daremos uma ideia da prova do seguinte resultado que obtivemos no contexto da segunda conjectura. Informalmente, para \(n\) suficientemente grande, sempre é possível empacotar perto de \(\sqrt{n}\) árvores quase geradoras no \(K_{n,n}\). Formalmente, para todo \(\gamma > 0\), existe \(n_0\) tal que, para todo \(n \geq n_0\), qualquer família de \(n^{\frac12-\gamma}\) árvores balanceadas em \(2(1-\gamma)n\) vértices pode ser empacotada no \(K_{n,n}\).
Este é um trabalho feito em conjunto com Tássio Naia, Giovanne dos Santos e Maya Stein.
- Yani Pehova (LSE)
31/03 (sexta-feira) – 14h – Local: Sala A241 (IME – Bloco A)
Título: Transversal factors and spanning trees
Resumo: In this talk we consider a recent transversal, or rainbow, variant of the classical question: for which \(d\) do \(n\)-vertex graphs with minimum degree \(d\) always contain a fixed subgraph \(H\)? We consider a collection of \(m\) graphs on the same set of \(n\) vertices whose minimum degree is at least \(d\), and ask which \(d\) guarantee the existence of a fixed (\(m\)-edge) subgraph \(H\) using exactly one edge from each graph in the collection. The obtained copy of \(H\) is called a transversal, or a rainbow copy if we view each graph as a different colour. We give asymptotically optimal minimum degree thresholds for the existence of rainbow spanning trees with maximum degree \(o(n/\log n)\) and perfect \(F\)-tilings in this setting.
This is joint work with Alp Müyesser and Richard Montgomery.
2022
- Carla Negri Lintzmayer (UFABC)
- Data: 27/10 – 14h – LOCAL: Sala B016 (IME – Bloco B)
Título: Arborescências folhudas em DAGs
Resumo: Este seminário resume os principais resultados que obtivemos em algoritmos de aproximação para o problema de encontrar árvores geradoras com número máximo de folhas em digrafos acíclicos, uma \(3/2\)-aproximação e uma \(7/5\)-aproximação, o que envolve a relação deste com outros problemas interessantes (emparelhamentos e conjuntos independentes).
Trabalho em conjunto com Cristina G. Fernandes.
- Victor Sanches Portella (University of British Columbia)
- Data: 21/10 – 14h
Título: Quando Online Learning encontra Cálculo Estocástico
Resumo: Online learning (OL) é um modelo teórico de aprendizado de máquina que relaxa as hipóteses típicas feitas sobre a fonte de dados. Um dos casos mais fundamentais de OL é o problema de predição com ajuda de experts. Nele, um jogador tem que fazer uma sequência de predições, por exemplo, predizer a cada dia se choverá ou não no dia seguinte. Ao invés de fazer a predição sem nenhuma informação, o jogador tem acesso a dicas de um conjunto de experts. Em cada rodada, o jogador escolhe um dos experts, possivelmente de forma aleatorizada, cuja sugestão ele vai seguir. Depois de cada escolha do jogador, um adversário decide quais experts estavam certos. Mesmo com a natureza adversarial desse modelo, existem estratégias que permitem o jogador de certa forma predizer tão bem quanto o melhor dos experts. Para além de OL, esse problema tem aplicações em várias áreas, tais como boosting, otimização combinatória, privacidade, dentre outras.
O problema dos experts é um clássico de OL. No entanto, ainda existem perguntas em aberto sobre ele. Por exemplo: será que um jogador que sabe de antemão o número de predições que terá que fazer no total é um melhor preditor do que um que não tem essa mesma informação? Essa pergunta nos levou a estudar uma versão do problema dos experts em que, ao invés de uma sequência discreta de decisões, o jogador faz uma predição em todo instante de tempo de forma contínua. Nesta palestra, farei uma breve introdução ao problema dos experts e algumas de suas aplicações. Em seguida, discutirei o modelo com tempo contínuo, como podemos desenvolver estratégias para o jogador usando cálculo estocástico, e como podemos em alguns casos transferir esses algoritmos e resultados de volta ao caso discreto.
Parte desse trabalho foi em conjunto com Nick Harvey, Chris Liaw, e Laura Greenstreet.
- Cláudio Lucchesi (USP)
- Data: 07/10 – 14h
Título: Grafos cobertos por emparelhamentos
Resumo: Um grafo é coberto por emparelhamentos (gce) se é conexo e toda aresta pertence a um emparelhamento perfeito. Os grafos cúbicos 2-aresta-conexos são todos cobertos por emparelhamentos. Os exemplos mais ilustres de gce são o $K_4$, o prisma triangular e o grafo de Petersen.
A origem desse estudo está no final do século 19, com o então Problemas das 4 cores. Mas recentemente tem havido muito progresso, com teoremas bonitos e conjecturas atraentes. Em particular há um teorema, cuja demonstração, do Lovász, com certeza está no livro de Deus de Erdős.
Pretendemos dar uma amostra da área para degustação, também com apresentação de alguns problemas em aberto e conjecturas interessantes.
Em coautoria com U. S. R. Murty, estamos prestes a enviar para publicação o livro “Perfect Matchings: A Theory of Matching Covered Graphs”.
Outro livro básico na área é o livro de Lovász e Plummer, “Matching Theory”.
- Leonardo Nagami Coregliano (IAS Princeton)
- Data: 25/08 – 14h
Título: O número cromático abstrato
Resumo: Qual é a densidade de um grafo que garante que ele conterá uma cópia de um subgrafo em particular? Ou que ele conterá um subgrafo em uma família \(\mathcal{F}\) ? O célebre Teorema de Erdős–Stone–Simonovits caracteriza a densidade máxima de grafos livres de cópias de \(\mathcal{F}\) em termos do mínimo dos números cromáticos dos grafos em \(\mathcal{F}\). Recentemente, generalizações desse teorema para grafos ordenados, grafos ciclicamente ordenados, grafos com arestas ordenadas, etc. foram provadas em termos de variantes do número cromático.
Em um trabalho recente com A. Razborov, um resultado análogo desse teorema foi provado no contexto de “grafos com estrutura extra arbitrária” (formalmente, esse contexto é capturado por interpretações abertas da teoria de grafos em uma teoria universal de primeira-ordem \(T\)) em termos de um número cromático abstrato. Porém, como o nome sugere, a primeira fórmula para tal número cromático abstrato é tão abstrata que sua computabilidade foi deixada como problema aberto.
Nesta palestra, apresentarei essa generalização do teorema de Erdős–Stone–Simonovits, e uma fórmula alternativa para o número cromático abstrato que se baseia em uma versão partida do teorema de Ramsey. Uma consequência de tal fórmula alternativa é a computabilidade do número cromático abstrato quando a teoria universal \(T\) subjacente é finitamente axiomatizável.
Esta palestra não requererá nenhum conhecimento prévio.