Mostre que se
for um número inteiro positivo com
, então o número de Ramsey
é igual a
.
Passo 1
O enunciado pede para provar que, para todo inteiro positivo
, vale
onde
é o menor inteiro
tal que, em qualquer coloração das arestas de
em duas cores (vermelho e azul), existe um clique vermelho de tamanho
ou um clique azul de tamanho
.
Passo 2
(Prova de
)
Considere o grafo completo e colore todas as suas arestas de azul.
Considere o grafo completo
- Não há aresta vermelha, logo não existe clique vermelho de tamanho
. - Há apenas
vértices, logo não pode haver clique azul de tamanho .
Isso mostra que paraexiste uma coloração sem clique vermelho de tamanho nem clique azul de tamanho , ou seja,
Passo 3
(Prova de
)
Agora considere qualquer coloração das arestas de em vermelho e azul.
Agora considere qualquer coloração das arestas de
- Se existir ao menos uma aresta vermelha, ela já forma um clique vermelho de tamanho
. - Caso contrário, nenhuma aresta é vermelha, isto é, todas as
arestas são azuis, o que implica que todo é um clique azul de tamanho .
Em qualquer dos dois casos, garantimos a existência de um clique vermelho de tamanhoou de um clique azul de tamanho , logo
Resposta
Como mostramos
e
, concluímos que