Partitioning random graphs into monochromatic copies

• Grant number: 19/27350-8
• Support Opportunities: Scholarships in Brazil - Master
• Start date: April 01, 2020
• End date: June 30, 2022
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Guilherme Oliveira Mota
• Grantee: Juliane Kristine de Lima
• Host Institution: Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , SP, Brazil
• Associated research grant: 18/04876-1 - Ramsey theory, structural graph theory and applications in Bioinformatics, AP.JP

Abstract

Bal and DeBiasio presented a conjecture with respect to a threshold for the following Ramsey-type property for graphs G: in every edge-colouring of G with r colours, there exist r disjoint monochromatic trees that partition the vertex-set of G. Recently it was proved that for 2 colours, the threshold for this property is given by ((\log n)/n)^{1/2}.In this project, we will study this result in detail and we will investigate similar problems with respect to partitions and coverings of the vertex-set of G(n,p) in other monochromatic structures (e.g., paths, cycles). (AU)