Advanced search
Start date
Betweenand

Partitioning random graphs into monochromatic copies

Grant number: 19/27350-8
Support type:Scholarships in Brazil - Master
Effective date (Start): April 01, 2020
Effective date (End): March 31, 2022
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Guilherme Oliveira Mota
Grantee:Juliane Kristine de Lima
Home 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)