Numero de Ramsey relativo a arestas de potencias de caminhos
Given graphs G and H and a positive integer q we say that G is qRamsey for H if every q colouring of the edges of G contains a monochromatic copy of H denoted G N pHqq. The size Ramsey number rpHq of a graph H is defined to be rpHq " mint|EpGq| G N pHq2u. Answering a question suggested by Conlon, we prove that rpP k n q " Opnq for every fixed k, where P k n is the kth power of the n vertex path Pn, i.e. the graph with vertex set V pPnq and all edges tu, vu such that the distance between u and v in Pn is at most k. Resumo. Dados grafos G e H e um inteiro positivo q, dizemos que G e qRamsey para H se toda q coloracao das arestas de G contem uma copia monocromatica de H Denotamos essa propriedade por G N pHqq. O numero de Ramsey relativo a arestas rpHq de um grafo H e definido como rpHq " mint|EpGq| G N pHq2u. Respondendo uma pergunta sugerida por Conlon, provamos que rpP k n q " Opnq para todo k fixo, onde P k n e a k esima potencia do caminho com n vertices Pn, i.e. o grafo com conjunto de vertices V pPnq e todas as arestas tu, vu tais que a distancia entre u e v em Pn e no maximo k. O terceiro autor foi apoiado pela FAPESP (2013/03447 6, 2013/07699 0) pelo CNPq (459335/20146, 310974/2013 5) e pelo Projeto MaCLinC/USP. O quinto autor foi apoiado pela FAPESP (2013/114312, 2013/03447 6) e parcialmente pelo CNPq (459335/2014 6) A colaboracao de parte dos autores foi apoiada pelo projeto CAPES/DAAD PROBRAL (430/15) Essa pesquisa foi realizada enquanto os autores participavam do ATI HIMR Focused Research Workshop: Large scale structures in random graphs