| Texto completo | |
| Autor(es): |
Clemens, Dennis
[1]
;
Jenssen, Matthew
[2]
;
Kohayakawa, Yoshiharu
[3]
;
Morrison, Natasha
[4]
;
Mota, Guilherme Oliveira
[5]
;
Reding, Damian
[1]
;
Roberts, Barnaby
[2]
Número total de Autores: 7
|
| Afiliação do(s) autor(es): | [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
Número total de Afiliações: 5
|
| Tipo de documento: | Artigo Científico |
| Fonte: | JOURNAL OF GRAPH THEORY; v. 91, n. 3, p. 290-299, JUL 2019. |
| Citações Web of Science: | 0 |
| Resumo | |
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) | |
| Processo FAPESP: | 13/11431-2 - Combinatória extremal e probabilística |
| Beneficiário: | Guilherme Oliveira Mota |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |
| Processo FAPESP: | 18/04876-1 - Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática |
| Beneficiário: | Guilherme Oliveira Mota |
| Modalidade de apoio: | Auxílio à Pesquisa - Jovens Pesquisadores |
| Processo FAPESP: | 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação |
| Beneficiário: | Carlos Eduardo Ferreira |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |