Mostre que se
e
forem números inteiros positivos com
e
, então os números de Ramsey
e
são iguais.
Passo 1
O enunciado quer mostrar que, para quaisquer inteiros positivos
e
, vale
onde
é o menor inteiro
tal que, em qualquer coloração das arestas de
com duas cores (digamos vermelho e azul), aparece necessariamente um
todo vermelho ou um
todo azul. Vamos usar a definição de número de Ramsey e um argumento de simetria trocando as cores para estabelecer as duas desigualdades que levam à igualdade.
Passo 2
Definição. Dizemos que
é o mínimo inteiro
com a propriedade: em toda coloração das arestas de
em vermelho e azul surge ou um
monocor vermelho ou um
monocor azul. Em símbolos, para todo mapeamento
existe um subgrafo completo de ordem
cujas arestas são todas vermelhas ou um subgrafo completo de ordem
cujas arestas são todas azuis.
Passo 3
Provar
. Seja
. Considere qualquer coloração
Defina uma nova coloração
trocando vermelho por azul e vice-versa em
. Como
, na coloração
aparece ou um
todo vermelho (em
) ou um
todo azul (em
). Mas isso significa, de volta em
, que ou existe um
todo azul ou um
todo vermelho. Logo
já satisfaz a propriedade de
, provando
Passo 4
Provar
. Basta repetir o mesmo argumento trocando os papéis de
com
. Tomando
e aplicando a troca de cores, obtemos
Passo 5
Das desigualdades
concluímos