Monochromatic trees in random graphs

Author(s)

Kohayakawa, Yoshiharu ^[1] ; Mota, Guilherme Oliveira ^[1] ; Schacht, Mathias ^[2]

Affiliation

^[1] Univ Sao Paulo, Inst Matemat & Estat, Rua Matao 1010, BR-05508090 Sao Paulo, SP - Brazil

^[2] Univ Hamburg, Fachbereich Math, Bundesstra SSe 55, D-20146 Hamburg - Germany

• Document type: Journal article
• Source: MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY; v. 166, n. 1, p. 191-208, JAN 2019.
• Web of Science Citations: 2

Abstract

Bal and DeBiasio {[}Partitioning random graphs into monochromatic components, Electron. J. Combin. 24 (2017), Paper 1.18] put forward a conjecture concerning the threshold for the following Ramsey-type property for graphs G: every k-colouring of the edge set of G yields k pairwise vertex disjoint monochromatic trees that partition the whole vertex set of G. We determine the threshold for this property for two colours. (AU)

• FAPESP's process: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science
• Grantee: Carlos Eduardo Ferreira
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 13/07699-0 - Research, Innovation and Dissemination Center for Neuromathematics - NeuroMat
• Grantee: Oswaldo Baffa Filho
• Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC
• FAPESP's process: 13/11431-2 - Extremal and probabilistic combinatorics
• Grantee: Guilherme Oliveira Mota
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• FAPESP's process: 13/20733-2 - Extremal and probabilistic combinatorics
• Grantee: Guilherme Oliveira Mota
• Support Opportunities: Scholarships abroad - Research Internship - Post-doctor