Anti-Ramsey properties: non-existence of rainbow copies

• Grant number: 21/09306-1
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: September 01, 2021
• End date: August 31, 2022
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computational Mathematics
• Principal Investigator: Guilherme Oliveira Mota
• Grantee: Victor Manuel Dias Saliba
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 18/04876-1 - Ramsey theory, structural graph theory and applications in Bioinformatics, AP.JP

Abstract

In this project, we are interested in studying the fundamental concepts related to random graphs in order to investigate recent research results on anti-Ramsey problems. We are interested in investigating the following problem: given a fixed graph $H$ and a random binomial graph $G(n,p)$, what is the greatest value of $p$ such that there is a proper coloring of the edges of $G(n,p)$ that does not contain a multicolored copy of $H$ with high probability. In the initial phase of this project, the student will study book chapters about random graphs, obtaining the necessary knowledge to start research in the area. In a second moment, the student will work towards understanding recent research articles on the topic, learning the techniques used to prove $0$-statements in Ramsey and anti-Ramsey problems. (AU)