Logo CombO

Seminars of CombΘ

In the seminars of our research group, we have presentations from group members and by visiting researchers at the Institute of Mathematics of USP.

2025 seminars
  • Francesco Di Braccio (LSE)

    • 07/03 (sexta-feira) - 14h - Local: To be announced.

    • Title: The Zarankiewicz problem on tripartite graphs

    • Abstract: In 1975, Bollobás, Erdős, and Szemerédi asked for the smallest τ such that an n × n × n tripartite graph with minimum degree n + τ must contain Kt,t,t , conjecturing that τ = O(n 1/2) for t = 2. We prove that τ = O(n 1−1/t ) which confirms their conjecture and is best possible assuming the widely believed conjecture that ex(n, Kt,t) = Θ(n 2−1/t ). Our proof uses a density increment argument. We also construct an infinite family of extremal graphs.
      This is joint work with Freddie Illingworth.

  • Meysam Miralaei (USP)
    • To be announced
    • Title: To be announced
  • Cristiane Maria Sato (Universidade Federal do ABC - UFABC)
    • To be announced
    • Title: From MAXCUT to infinity and beyond: a general framework
2024 seminars
  • Cristiane Maria Sato (Universidade Federal do ABC - UFABC)

    • 29/11 (sexta-feira) - 15h30 - Local: Auditório Imre Simon (CCSL)

    • Title: MAXCUT: a meeting point of graph theory, optimization and probability

    • Abstract: The MAXCUT problem has a long and rich history, involving many elegant results in approximation algorithms, polyhedral methods, linear and nonlinear optimization, and probabilistic techniques. In this work, we study a weighted generalization of the fractional cut-covering problem (FCC) and establish its connection to the MAXCUT problem through antiblocker theory and gauge duality. This connection enables us to propose a semidefinite programming (SDP) relaxation, whose solutions can be rounded into fractional cut covers using the random hyperplane technique introduced by Goemans and Williamson. Our main contribution is an algorithm that integrates these components to simultaneously approximate both MAXCUT and FCC instances by solving a single SDP.
      This is joint work with N. Benedetto Proença, M.K. de Carli Silva, and L. Tunçel.

  • Patrick Morris (Universitat Politècnica de Catalunya - UPC)

    • 21/11 (quinta-feira) - 14h - Local: Auditório Antonio Gilioli

    • Title: Rainbow loose Hamilton cycles in Dirac hypergraphs

    • Abstract: A meta-conjecture of Coulson, Keevash, Perarnau and Yepremyan states that above the extremal threshold for a given spanning structure in a (hyper-)graph, one can find a rainbow version of that spanning structure in any suitably bounded colouring of the host (hyper-)graph. We solve one of the most pertinent outstanding cases of this conjecture, by showing that for any 1 ≤ j ≤ k-1, if G is a k-graph above the j-degree threshold for a loose Hamilton cycle, then any globally bounded colouring of G contains a rainbow loose Hamilton cycle.
      This represents joint work with Amarja Kathapurkar and Guillem Perarnau.

  • Marcelo Sales (University of California)

    • 8/11 (sexta-feira) - 15h30 - Local: Sala Multiuso do NUMEC

    • Title: Covering random digraphs with Hamilton cycles

    • Abstract: A covering of a digraph D by Hamilton cycles is a collection of directed Hamilton cycles (not necessarily edge-disjoint) that together cover all the edges of D. In this talk we show that for 1/2 >= p >= ((\log n)^{20})/n, the random digraph D_{n,p} typically admits an optimal Hamilton cycle covering. Specifically, the edges of D_{n,p} can be covered by a family of t Hamilton cycles, where t is the maximum of the the in-degree and out-degree of the vertices in D_{n,p}. Notably, t is the best possible bound, and our assumption on p is optimal up to a polylogarithmic factor.
      This is joint work with Asaf Ferber and Mason Shurman.

  • Victor Portella (USP)

    • 1/11 (sexta-feira) - 14h - Local: Sala Multiuso do NUMEC

    • Title: Uma Introdução a Privacidade Diferencial e Técnicas de Fingerprinting para Cotas Inferiores

    • Abstract: A análise de dados sensíveis sempre apresentou um dilema fundamental: como extrair informações sobre características de uma população enquanto se protege a privacidade de indivíduos? Após um histórico de métodos ad hoc e heurísticas, a Privacidade Diferencial (PD) emergiu como uma resposta matemática rigorosa a este desafio, oferecendo garantias formais sobre o risco de exposição de informações sensíveis. Desde sua proposição, a área de PD avançou rapidamente, com suas técnicas sendo adotadas por grandes empresas e incorporadas até mesmo pelo Censo Decenal dos Estados Unidos. Além das aplicações em análise de dados sensíveis, a comunidade de pesquisa tem descoberto conexões surpreendentes entre PD e diversas áreas como online learning, análise adaptativa de dados, generalização em aprendizado de máquina e estatística robusta.
      Nesta palestra, apresentarei uma breve introdução à Privacidade Diferencial e discutirei algumas das suas mais importantes conexões com outros conceitos em Ciência da Computação. Em seguida, abordarei técnicas de fingerprinting para obter cotas inferiores para diversos problemas em privacidade diferencial, desde o uso de códigos de fingerprinting – originalmente propostos na área de criptografia para rastreamento de conteúdo digital – até sua evolução para Lemas de Fingerprinting, concluindo com resultados recentes obtidos em colaboração com o Prof. Nick Harvey da University of British Columbia.

  • Leonardo Nagami Coregliano (The University of Chicago)

    • 30/8 (sexta-feira) – 14h – Local: Sala Multiuso do NUMEC

    • Title: High-arity PAC learning via exchangeability

    • Abstract: Classic PAC learning theory studies when we can make an accurate guess of a set based on finitely many i.i.d. samples from it. The Fundamental Theorem of Statistical Learning characterizes when such an accurate guess can be made in terms of the Vapnik–Chervonenkis dimension. The natural generalization of PAC learning functions has also been characterized in terms of the Natarajan dimension (when the co-domain is finite) and in terms of the Daniely–Shalev-Shwartz dimension (for arbitrary co-domains). In this talk, we will explore a different generalization, called high-arity PAC learning, that is motivated by PAC learning of graphs, hypergraphs and relational structures and relies on exchangeability theory. We will cover the basic definitions, the statement of the high-arity Fundamental Theorem, some proof ideas and mention the furthest reaches of the theory covering “PAC learning for (quasi)random graphs”.
      No prior knowledge of learning theory or exchangeability theory will be required.

      This talk is based on joint work with Maryanthe Malliaris.

  • Julia Boettcher (LSE)

    • 16/8 (sexta-feira) – 14h00 – Local: Sala Multiuso do NUMEC

    • Title: Graph universality

    • Abstract: Given a class G of n-vertex graphs, how can we construct a host graph H that contains them all as subgraphs? Graphs H with this property are called universal for G, and the question gets interesting when we put certain restrictions on H. For example, we might be interested in a graph H with as few edges as possible, or a graph H which has only n vertices itself and still only few edges. Or we might ask when certain random graphs are universal for G. This all leads to a variety of interesting and challenging problems. In the talk, I will explain what is known and what is open for some classes of graphs G. I will also detail some techniques that I recently used with my co-authors Peter Allen and Anita Liebenau for progress when G consists of all D-degenerate graphs for a fixed D.

  • Joseph Hyde (University of Victoria)

    • 7/6 (sexta-feira) – 15h30 – Local: Auditório do NUMEC

    • Title: Thresholds for random Ramsey problems

    • Abstract: The study of Ramsey properties of the binomial random graph 𝐺𝑛,𝑝 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 𝑓(𝑛) governs 𝐺𝑛,𝑝 having a particular Ramsey-like property 𝑃 or not, i.e. when 𝑝 is sufficiently larger than 𝑓(𝑛) then 𝐺𝑛,𝑝 a.a.s. has 𝑃 and when 𝑝 is sufficiently smaller than 𝑓(𝑛) then 𝐺𝑛,𝑝 a.a.s. does not have 𝑃 (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)

    • Title: Circuitos monótonos e o problema do clique

    • Abstract: 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 Clique𝑛,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.

  • Francisco Calvillo Marmaneu (Universidade Pompeu Fabra)

    • 3/5 (sexta-feira) – 15h – Local: Auditório Jacy Monteiro (Bloco B)

    • Title: Archeology in random graphs: root-finding methods in large growing networks

    • Abstract: 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)

    • Title: A branch-and-cut algorithm for the availability-aware VNF placement problem in virtualized networks

    • Abstract: 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.

Miniseries of seminars on recent results regarding the problem of separating edges by paths. The results described in the following works will be presented:

– 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)

    • Title: Small weakly separating path systems for complete graphs

    • Abstract: 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.

  • Guilherme Mota (USP)

    • 19/4 (sexta-feira) – 14h – Local: A249 (Bloco A)

    • Title: Sistemas de separação por caminhos em grafos completos

    • Abstract: Mostraremos que em qualquer grafo completo com 𝑛 vértices há uma coleção 𝑃 de (1+𝑜(1))𝑛 caminhos que separa fortemente qualquer par {𝑒,𝑓} de arestas distintas, isto é, há um caminho em 𝑃 que contém a aresta 𝑒, mas não contém a aresta 𝑓, e outro caminho em 𝑃 que contém a aresta 𝑓 mas não contém a aresta 𝑒. Além disso, para certas classes de grafos 𝛼𝑛-regulares com 𝑛 vértices, encontramos uma coleção de (sqrt(3𝛼+1)–1+𝑜(1))𝑛 caminhos que separa fortemente qualquer par de arestas. Ambos os resultados são os melhores possíveis a menos do termo 𝑜(1).

      Trabalho em conjunto com Cristina Gomes Fernandes e Nicolás Sanhueza-Matamala.

  • Fábio Botler (USP)

    • 12/4 (sexta-feira) – 14h – Auditório Jacy Monteiro (Bloco B)

    • Title: Separating the edges of a graph by a linear number of paths

    • Abstract: Recently, Letzter proved that any graph of order 𝑛 contains a collection of 𝑂(𝑛log⋆𝑛) paths with the following property: for all distinct edges 𝑒 and 𝑓 there exists a path in which contains 𝑒 but not 𝑓. We improve this upper bound to 19𝑛, 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 – Auditório Imre Simon (CCSL)

    • Title: Jogos, Quebra-Cabeças e Complexidade Computacional

    • Abstract: 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)

  • Marcelo Campos (Universidade de Cambridge)

    • 8/3 (sexta-feira) – 14h – Sala B03 (IME – Bloco B)

    • Title: A new lower bound for sphere packing

    • Abstract: We show there exists a packing of identical spheres in ℝ𝑑 with density at least (1−𝑜(1))𝑑log𝑑2𝑑+1 as 𝑑→∞. This improves upon previous bounds for general 𝑑 by a factor of order log𝑑 and is the first asymptotically growing improvement to Rogers’ bound from 1947.\

      Joint work with Matthew Jenssen, Marcus Michelen, Julian Sahasrabudhe.

2023 seminars

  • Marcelo Campos (Universidade de Cambridge)

    • 15/12 (sexta-feira) - 14h - Auditório Jacy Monteiro (IME – Bloco B)

    • Title: Número de independência de grafos de Cayley mais esparsos

    • Abstract: Dado 𝐴⊆ℤ𝑛 𝑝-aleatório, o grafo de Cayley aleatório Γ𝑝 é definido com tendo vértices ℤ𝑛 e uma aresta entre 𝑥,𝑦∈ℤ𝑛 se 𝑥+𝑦∈𝐴. Para 𝑝=1/2, Green e Morris mostraram que o número de independência de Γ1/2 é assintoticamente igual a 𝛼(𝐺(𝑛,1/2)), com alta probabilidade. Neste seminário vou mostrar que o número de independência de Γ𝑝 se iguala ao de 𝐺(𝑛,𝑝) para 𝑝≥(log𝑛)−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 – Sala A241 (IME – Bloco A)

    • Title: The Goemans and Williamson Algorithm Extended to the Weighted Fractional Cut-Covering Problem

    • Abstract: 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 - Sala A241 (IME – Bloco A)

    • Title: Ramsey-bondade em grafos densos

    • Abstract: Dizemos que um grafo 𝐺 é Ramsey para o par de grafos (𝐹,𝐻), se em toda coloração das arestas de 𝐺 com as cores vermelho e azul, existe uma cópia vermelha de 𝐹 ou uma cópia azul de 𝐻. Chvátal mostrou que o grafo completo 𝐾𝑛 é Ramsey para o par (𝐾𝑟,𝑃𝑡), para 𝑛≥(𝑟−1)(𝑡−1)+1. Neste seminário, generalizaremos o teorema de Chvátal mostrando que para qualquer grafo 𝐺 com 𝑛=(𝑟−1)(𝑡−1)+1 vértices e 𝛿(𝐺)≥𝑛–𝑡/2, temos que 𝐺 é Ramsey para (𝐾𝑟,𝑃𝑡). 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 – Sala A241 (IME – Bloco A)

    • Title: A Canonical Ramsey Theorem with List constrains in G(n,p)

    • Abstract: 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 – Sala A241 (IME – Bloco A)

    • Title: Jogando “20 perguntas” sobre grafos

    • Abstract: Dez anos atrás, G.O.H. Katona propôs o problema determinar, para cada grafo 𝐺, qual o menor tamanho de uma coleção de caminhos 𝑃1,…,𝑃𝑡 em 𝐺 com a seguinte propriedade: para qualquer par {𝑔,ℎ} de arestas distintas de 𝐺, algum 𝑃𝑖 intersecta {𝑔,ℎ} em apenas 𝑔 ou apenas ℎ. Dizemos que essa coleção de caminhos separa as arestas de 𝐺. 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)

    • Title: Cycle decompositions in hypergraphs

    • Abstract: A cycle decomposition of a hypergraph 𝐺 is an edge-disjoint collection of cycles which use every edge of 𝐺. 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)

    • Title: Empacotamento de árvores balanceadas quase geradoras no 𝐾𝑛,𝑛 (ou… minha saga com o Lema da Regularidade)

    • Abstract: Em 1976, Gyárfas conjecturou que qualquer sequência de árvores 𝑇1,…,𝑇𝑛, onde 𝑇𝑖 tem ordem 𝑖, pode ser empacotada no 𝐾𝑛. Mais recentemente, em 2013, Hollingsworth apresentou uma variante bipartida desta conjectura, que diz que qualquer sequência de árvores 𝑇1,1,…,𝑇𝑛,𝑛, onde 𝑇𝑖,𝑖 tem 𝑖 vértices em cada lado da sua bipartição, pode ser empacotada no 𝐾𝑛,𝑛. 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 𝑛 suficientemente grande, sempre é possível empacotar perto de 𝑛√ árvores quase geradoras no 𝐾𝑛,𝑛. Formalmente, para todo 𝛾>0, existe 𝑛0 tal que, para todo 𝑛≥𝑛0, qualquer família de 𝑛12−𝛾 árvores balanceadas em 2(1−𝛾)𝑛 vértices pode ser empacotada no 𝐾𝑛,𝑛.

      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)

    • Title: Transversal factors and spanning trees

    • Abstract: In this talk we consider a recent transversal, or rainbow, variant of the classical question: for which 𝑑 do 𝑛-vertex graphs with minimum degree 𝑑 always contain a fixed subgraph 𝐻? We consider a collection of 𝑚 graphs on the same set of 𝑛 vertices whose minimum degree is at least 𝑑, and ask which 𝑑 guarantee the existence of a fixed (𝑚-edge) subgraph 𝐻 using exactly one edge from each graph in the collection. The obtained copy of 𝐻 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 𝑜(𝑛/log𝑛) and perfect 𝐹-tilings in this setting.

      This is joint work with Alp Müyesser and Richard Montgomery. 2022

  • Marcelo Campos (IMPA)

    • 16/3 (quinta-feira) - 16h - Auditório Imre Simon (CCSL)

    • Title: Progresso em um problema de Erdős

    • Abstract: 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

    • Abstract do manuscrito: The Ramsey number 𝑅(𝑘) is the minimum 𝑛∈ℕ such that every red-blue colouring of the edges of the complete graph 𝐾𝑛 on 𝑛 vertices contains a monochromatic copy of 𝐾𝑘. We prove that 𝑅(𝑘)≤(4−𝜀)𝑘 for some constant 𝜀>0. This is the first exponential improvement over the upper bound of Erdős and Szekeres, proved in

  • Carla Negri Lintzmayer (UFABC)

    • 27/10 – 14h – LOCAL: Sala B016 (IME – Bloco B)

    • Title: Arborescências folhudas em DAGs

    • Abstract: 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)

    • 21/10 – 14h - Auditório Imre Simon (CCSL)

    • Title: Quando Online Learning encontra Cálculo Estocástico

    • Abstract: 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)

    • 07/10 – 14h - Auditório Imre Simon (CCSL)

    • Title: Grafos cobertos por emparelhamentos

    • Abstract: 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)

    • 25/08 – 14h - Auditório Imre Simon (CCSL)

    • Title: O número cromático abstrato

    • Abstract: 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  ? O célebre Teorema de Erdős–Stone–Simonovits caracteriza a densidade máxima de grafos livres de cópias de  em termos do mínimo dos números cromáticos dos grafos em . 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 𝑇) 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 𝑇 subjacente é finitamente axiomatizável.

      Esta palestra não requererá nenhum conhecimento prévio.