Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

The size-Ramsey number of powers of paths

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
Linha de fomento: 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
Linha de fomento: Auxílio à Pesquisa - Apoio a Jovens Pesquisadores
Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático