On the Emergence of Unavoidable Combinatorial Structures in Graphs and Hypergraphs

• Grant number: 25/07186-0
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: October 01, 2025
• End date: September 30, 2028
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computational Mathematics
• Principal Investigator: Guilherme Oliveira Mota
• Grantee: Henrique Stagni
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 24/13859-4 - Ramsey Theory: from monochromatic to canonical structures, AP.R

Abstract

This project describes the postdoctoral research of Henrique Stagni, to be carried out under the supervision of Guilherme Mota, at the Instituto de Matemática e Estatística (IME-USP), from 06/01/2025 to 05/31/2028. This proposal is linked to the \emph{Auxílio Regular 2024/13859-4}, coordinated by the supervisor, and will significantly contribute to the advancement of one of the lines of the \emph{Projeto Temático 2023/03167-5}, coordinated by Yoshiharu Kohayakawa, a collaborator in the research proposed here.The main objective of this project is to achieve relevant advances in problems related to conditions that guarantee the emergence of certain unavoidable combinatorial structures in graphs and hypergraphs. We divide the study of this phenomenon into three distinct approaches.In the first, this phenomenon is studied for (deterministic) hypergraphs. More specifically, we propose problems related to the \emph{minimum degree conditions} required to ensure the emergence of certain structures in hypergraphs, such as spanning trees and perfect matchings.In the second approach, we address this type of phenomenon for random graphs, proposing problems related to \emph{Ramsey Theory}. More specifically, we study threshold functions that guarantee the existence of certain "canonical" structures that are unavoidable in arbitrary colorings of the random graph~$G(n,p)$.Finally, we analyze this type of phenomenon in a more quantitative way, proposing problems in \emph{property testing} --- the focus of this area is on determining how the distance to a given property causes a large number of local structures to emerge that witness the non-membership to that property. In particular, we study problems related to ``proximity-oblivious testers'' --- a more restrictive version of testers --- and problems about properties of (hypergraphs that represent) configurations of points in the plane.The candidate has an excellent academic background and previous experience in the topics to be investigated. The project supervisor is an experienced researcher in the field of extremal and probabilistic combinatorics, is the author of articles whose results and techniques will be valuable for investigating the proposed problems, and is also the coauthor of the book ``Combinatória''. (AU)