Stochastic chains with unbounded memory and random walks on graphs
| Full text | |
| Author(s): |
Kohayakawa, Yoshiharu
[1]
;
Mendonca, Walner
[2]
;
Mota, Guilherme Oliveira
[1]
;
Schuelke, Bjarne
[3]
Total Authors: 4
|
| Affiliation: | [1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508900 Sao Paulo, SP - Brazil
[2] Univ Warwick, Math Inst, Coventry CV4 7AL, W Midlands - England
[3] Univ Hamburg, Fachbereich Math, D-20146 Hamburg - Germany
Total Affiliations: 3
|
| Document type: | Journal article |
| Source: | SIAM JOURNAL ON DISCRETE MATHEMATICS; v. 35, n. 2, p. 1447-1459, 2021. |
| Web of Science Citations: | 0 |
| Abstract | |
We investigate the problem of determining how many monochromatic trees are necessary to cover the vertices of an edge-colored random graph. More precisely, we show that for p >> n(-1/6)(ln n)(1/6), in any 3-edge coloring of the random graph G(n, p) we can find three monochromatic trees such that their union covers all vertices. This improves, for three colors, a result of Bucic, Korandi, and Sudakov. (AU) | |
| FAPESP's process: | 18/04876-1 - Ramsey theory, structural graph theory and applications in Bioinformatics |
| Grantee: | Guilherme Oliveira Mota |
| Support Opportunities: | Research Grants - Young Investigators Grants |
| FAPESP's process: | 19/13364-7 - Extremal and structural problems in graph theory |
| Grantee: | Cristina Gomes Fernandes |
| Support Opportunities: | Regular Research Grants |