Mostre que se n for um número inteiro positivo com n \geq 2, então o número de Ramsey R(2, n) é igual a n.

Passo 1

O enunciado pede para provar que, para todo inteiro positivo n\ge2, vale
R(2,n)=n,
onde R(s,t) é o menor inteiro N tal que, em qualquer coloração das arestas de K_{N} em duas cores (vermelho e azul), existe um clique vermelho de tamanho s ou um clique azul de tamanho t.

Passo 2

(Prova de R(2,n)>n-1)
Considere o grafo completo K_{n-1} e colore todas as suas arestas de azul.
  • Não há aresta vermelha, logo não existe clique vermelho de tamanho 2.
  • Há apenas n-1 vértices, logo não pode haver clique azul de tamanho n.
    Isso mostra que para N=n-1 existe uma coloração sem clique vermelho de tamanho 2 nem clique azul de tamanho n, ou seja,
R(2,n)>n-1.

Passo 3

(Prova de R(2,n)\le n)
Agora considere qualquer coloração das arestas de K_{n} em vermelho e azul.
  • Se existir ao menos uma aresta vermelha, ela já forma um clique vermelho de tamanho 2.
  • Caso contrário, nenhuma aresta é vermelha, isto é, todas as \tfrac{n(n-1)}{2} arestas são azuis, o que implica que todo K_{n} é um clique azul de tamanho n.
    Em qualquer dos dois casos, garantimos a existência de um clique vermelho de tamanho 2 ou de um clique azul de tamanho n, logo
R(2,n)\le n.

Resposta

Como mostramos R(2,n)>n-1 e R(2,n)\le n, concluímos que
R(2,n)=n.

Exercícios relacionados