Extremal and structural problems in combinatorics

• Grant number: 25/27516-4
• Support Opportunities: Research Grants - Visiting Researcher Grant - Brazil
• Start date: March 01, 2026
• End date: February 28, 2027
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Guilherme Oliveira Mota
• Grantee: Guilherme Oliveira Mota
• Visiting researcher: Vinicius Fernandes dos Santos
• Visiting researcher institution: Instituto De Ciências Exatas/Icex/Ufmg , Brazil
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• City of the host institution: São Paulo
• Associated research grant: 23/03167-5 - Classical, asymptotic, quantum and geometric combinatorics, AP.TEM

Abstract

This project describes a research to be carried out at the Instituto de Matemática e Estatística (IME-USP) by the researcher Vinicius Fernandes dos Santos (UFMG) and his supervisor Guilherme O.\ Mota, in the period from 03/01/2026 to 02/28/2027.This research project aims to address central and challenging problems in Extremal and Structural Combinatorics, combining the visitor's expertise in Structural Graph Theory and Algorithms with that of the host group (CombO-USP). The scientific investigation is structured around three main axes: (i) the study of rainbow structures in deterministic and random graphs, focusing on variants of Lehel's Conjecture and thresholds in random graphs; (ii) advances on the celebrated Erd¿s Density Conjecture for triangle-free graphs, tackling open cases involving blow-ups of Vega graphs via vertex shifting techniques; and (iii) the resolution of conjectures on locally irregular decompositions, aiming to prove that the irregular chromatic index is bounded by 3 for broad classes of graphs. In addition to high-level scientific contributions, the plan includes a strong component of dissemination and consolidation of the area in Brazil, including the organization of major events, the ``Combinatorics Tour'' in emerging regions, and the introduction of Parameterized Complexity to the host group, fostering a deep and lasting integration between the involved institutions. (AU)