| Full text | |
| Author(s): |
Clemens, Dennis
[1]
;
Jenssen, Matthew
[2]
;
Kohayakawa, Yoshiharu
[3]
;
Morrison, Natasha
[4]
;
Mota, Guilherme Oliveira
[5]
;
Reding, Damian
[1]
;
Roberts, Barnaby
[2]
Total Authors: 7
|
| Affiliation: | [1] Tech Univ Hamburg, Inst Math, Hamburg - Germany
[2] London Sch Econ, Dept Math, London - England
[3] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
[4] Univ Cambridge, Dept Pure Math & Math Stat, Cambridge - England
[5] Univ Fed ABC, Ctr Matemat Comp & Cognicao, Ave Estados 5001, BR-09210580 Santo Andre, SP - Brazil
Total Affiliations: 5
|
| Document type: | Journal article |
| Source: | JOURNAL OF GRAPH THEORY; v. 91, n. 3, p. 290-299, JUL 2019. |
| Web of Science Citations: | 0 |
| Abstract | |
Given graphs G and H and a positive integer q, say that G is q-Ramsey for H, denoted G -> (H)(q), if every q-coloring of the edges of G contains a monochromatic copy of H. The size-Ramsey number (r) over cap (H) of a graph H is defined to be (r) over cap (H) = min[vertical bar E (G)vertical bar: G -> (H)(2)]. Answering a question of Conlon, we prove that, for every fixed k, we have (r) over cap (P-n(k)) = O(n), where P-n(k) is the kth power of the n-vertex path P-n (ie, the graph with vertex set V(P-n) and all edges [u, v] such that the distance between u and v in Pn is at most k). Our proof is probabilistic, but can also be made constructive. (AU) | |
| FAPESP's process: | 13/11431-2 - Extremal and probabilistic combinatorics |
| Grantee: | Guilherme Oliveira Mota |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| 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: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |