Número de Ramsey relativo a arestas de potências de caminhos - Clemens, Dennis; Jenssen, Matthew; Kohayakawa, Yoshiharu; Morrison, Natasha; Mota, Guilherme Oliveira; Reding, Damian; Roberts, Barnaby (Anais do Encontro de Teoria da Computação (ETC), 2017)
Dados grafos G e H e um inteiro positivo q, dizemos que G é q-Ramsey para H se toda q-coloração das arestas de G contém uma cópia monocromática de H. Denotamos essa propriedade por G ⭢ (H) q . O número de Ramsey relativo a arestas r̂(H) de um grafo H é definido como r̂(H) = min{|E(G)|: G ⭢ (H) 2 }. Respondendo uma pergunta sugerida por Conlon, provamos que r̂(P n k ) = O(n) para todo k fixo, onde P n k é a k-ésima potência do caminho com n vértices P n , i.e., o grafo com conjunto de vértices V(P n ) e todas as arestas {u, v} tais que a distância entre u e v em P n é no máximo k.