This research project explores key challenges in combinatorics, with an emphasis on classical, asymptotic, quantum, and geometric problems. The initiative brings together a renowned team to tackle deep and original questions through interdisciplinary techniques, combining the expertise of the researchers of our team. It aims to advance the frontiers of mathematical knowledge in the field and to foster the next generation of researchers. Activities to be developed over the course of the project include the organization of schools, workshops, and collaborations among researchers from various groups in Brazil and abroad.

• Process Number: 2023/03167-5​
• Funding Line: Thematic Research Project​
• Duration: April 1, 2025, to March 31, 2030​
• Title: CLASSQG: Classical, Asymptotic, Quantum, and Geometric Combinatorics

Members

Research team

​Our research team comprises distinguished researchers from various institutions, including the University of São Paulo (USP), University of Campinas (UNICAMP), Federal University of Rio Grande do Sul (UFRGS), Federal University of ABC (UFABC), Federal University of Minas Gerais (UFMG), Federal University of Ceará (UFC), Federal University of Bahia (UFBA), and the Institute for Pure and Applied Mathematics (IMPA), as well as international collaborators. Led by Professor Yoshiharu Kohayakawa from USP, the team brings together experts in Combinatorics, Optimization, Quantum Mathematics and Theoretical Computer Science.

Principal investigators

Yoshiharu Kohayakawa (IME-USP)
Cláudio Leonardo Lucchesi (IME-USP)
Marcelo de Oliveira Terra Cunha (IMECC-Unicamp)
Orlando Lee (Instituto de Computação-Unicamp)
Sinai Robins (IME-USP)

Associate researchers

Bárbara Lopes Amaral (IF-USP)
Candida Nunes da Silva (UFSCAR)
Carlos Hoppen (UFRGS)
Cristiane Maria Sato (UFABC)
Cristina Gomes Fernandes (IME-USP)
Fabricio Siqueira Benevides (UFC)
Fábio Happ Botler (IME-USP)
Gabriel de Morais Coutinho (UFMG)
Guilherme Oliveira Mota (IME-USP)
Hiep Han (Universidad de Santiago de Chile)
Lucas Colucci Cavalcante de Souza (IME-USP)
Marcel Kenji de Carli Silva (IME-USP)
Marcelo Soares Campos (IMPA)
Mathias Schacht (Universität Hamburg)
Maurício de Lemos Rodrigues Collares Neto (IME-USP)
Maycon Sambinelli (UFABC)
Meysam Miralaei (IME-USP)
Nicolás Sanhueza Matamala (Universidad de Concepción)
Patrick Wyndham Morris (Universitat Politècnica de Catalunya)
Richard Lang (Universitat Politècnica de Catalunya)
Robert Morris (IMPA)
Roberto Freitas Parente (UFBA)
Tássio Naia dos Santos (Universitat Politècnica de Catalunya)
Victor Sanches Portella (IME-USP)
Walner Mendonça dos Santos (UFC)
Yoshiko Wakabayashi (IME-USP)

Research workshops

2 - 2nd Research Workshop CLASSQG - January 26 to 30, 2026

Participants
Cristiane Maria Sato (UFABC)
Carlos Hoppen (UFRGS)
Fábio Happ Botler (IME-USP)
Guilherme Oliveira Mota (IME-USP)
Maurício Collares (IME-USP)
Taísa Martins (UFF)
Vinicius Fernandes (UMFG)
Walner Mendonça (UFC)
Yoshiharu Kohayakawa (IME-USP)

Workshop activities
Research: Groups of the participants worked on Separation problems, and problems on Ramsey Theory and random graphs.

Program
From Monday to Friday we follow the program below:

Brief report

The participants worked on two groups, attacking different problems. One group was composed of Cristiane Sato, Carlos Hoppen, Fábio Botler and Vinicius dos Santos, and the other group was composed of Guilherme Mota, Maurício Collares Neto, Taísa Martins, Walner dos Santos and Yoshiharu Kohayakawa. The two groups exchanged ideas and information on the problems during the week.

The first group worked on separation problems. The group searched for variations of the problem of linear separating path systems that was recently solved by Bonamy, Botler, Dross, Naia and Skokan, in which one seeks for a system $S$ of paths in a given graph $G$ with the property that for each pair $(e,f)$ of edges of $G$ there is a path in $S$ that contains $e$ but does not contain $f$.

The group started studying the case of separating matchings systems. More specifically, it was proved that one can separate the edges of a graph with $n$ vertices and maximum degree $\Delta$ by at most $\Delta \log n$ matchings, and also by at most $\sqrt{\delta \cdot n}$ matchings. Then, they proceeded to improve these upper bounds, or find matching lower bounds.

Another direction was to generalize these results to separating systems consisting of elements of an hereditary family, and also that separates other discrete structures, as, for example, (i) separating the vertices of a graph by independent sets, and (ii) separating the ground set of a matroid by independent sets. The results obtained for separating matching systems above can be generalized to these cases.

The second group focused on problems in Ramsey Theory and random graphs, and was composed of Guilherme Mota, Maurício Collares Neto, Taísa Martins, Walner dos Santos and Yoshiharu Kohayakawa. The group investigated fundamental questions concerning thresholds in random graphs $G(n,p)$, extending beyond the classical monochromatic case solved by Rödl and Ruciński. Specifically, the research addressed thresholds for finding rainbow and also canonical (monochromatic, rainbow or lexicographic) copies of graphs.

This investigation builds on recent advances by Kohayakawa, Mota, and collaborators on the anti-Ramsey threshold, as well as on a recent result by Kamcev and Schacht, who determined the threshold for canonical copies of complete graphs, and a recent result by Alvarado, Mota, Kohayakawa, and Morris on the threshold for canonical copies of even cycles. The main objective was to understand the interplay between these different Ramsey properties and their respective thresholds, aiming to start the systematic study of the following question: given three graphs $H_1$, $H_2$, $H_3$, what is the threshold for finding a monochromatic copy of $H_1$, or a rainbow copy of $H_2$, or a lexicographic copy of $H_3$? Clearly, answering this question in full generality is a very hard problem, as even the case where $H_1$ is a path of length 2 is already very hard. In fact, this is the anti-Ramsey problem for $H_2$, as forbidding a path of length 2 is equivalent to forcing the colouring to be proper.

The starting point is to consider the case where all three graphs are complete graphs of any sizes (possibly different). The first non-trivial case considered was when $H_1 = K_3$, $H_2 = K_4$ and $H_3 = K_5$. Part of this research was continued right after this workshop, in another small workshop (see [Friends in Extremal Combinatorics ] (https://www.ime.usp.br/~mota/events/friends-extremal-combinatorics/), at IMPA, in Rio de Janeiro, where Walner Mendonça, Guilherme Mota, together with some collaborators from our FAPESP Thematic Project and 5 PhD students from USP, worked on this and related topics.

1 - 1st Research Workshop CLASSQG - August 3 to 8, 2025

Participants
César Bispo (USP)
Fábio Happ Botler (IME-USP)
Marcelo Campos (IMPA)
Maurício Collares (IME-USP)
Cristina Gomes Fernandes (IME-USP)
Simon Griffiths (PUC-Rio)
Yoshiharu Kohayakawa (IME-USP)
George Kontogeorgiou (Universidad de Chile)
Marcelo Lage (USP)
Walner Mendonça (UFC)
Meysam Miralaei (IME-USP)
Guilherme Oliveira Mota (IME-USP)
Victor Sanches Portella (IME-USP)

Workshop activities
Special talk: Marcelo Campos (IMPA) and Simon Griffiths (PUC-Rio) gave a talk on 06/08 about their major breakthrough on Ramsey Theory obtained together with Robert Morris and Julian Sahasrabudhe.

Research: Groups of the participants worked on problems on Ramsey Theory, random graphs and Separation path problems.

Brief report

The participants worked on various problems, related with the topics of the workshop. A reasonable time was spent on a conjecture of Erdős, which states that any triangle free graph with $n$ vertices contains a set of $\lfloor n/2 \rfloor$ vertices that contains at most $n^2/50$ edges. Problems of covering random graphs with monochromatic structures were also considered and gave rise to new projects on this.

Many subgroups of the participants had been working on related problems before the workshop, and the workshop was a good opportunity to make progress on these problems. For example, Cristina Fernandes, George Kontogeorgiou and Guilherme Mota finished the writting of a paper on separation path systems for bipartite graphs; Walner Mendonça, Meysam Miralaei and Guilherme Mota made some progress on a work concerning some Folkman-type problem.

Research visits

• Guilherme Mota and the students César Bispo (PhD) and Marcelo Lage (Undergrad) participated in the Santiago summer workshop in combinatorics, from January 12 to 16, 2026 (https://sites.google.com/view/combinatoricssantiago/inicio). In this ocasion, Guilherme Mota gave a talk and they worked together with George Kontogeorgiou (Universidad de Chile) and the master student Bruno Skarmeta (Universidad de Chile) on a problem on covering graphs with monochromatic components.

• Gabriel Coutinho (UFMG) visited Marcel Kenji de Carli Silva (USP) from July 30 to August 3, 2025, to do research on Quantum Combinatorics problems.