Mostre que se m e n forem números inteiros positivos com m \geq 2 e n \geq 2, então os números de Ramsey R(m, n) e R(n, m) são iguais.

Passo 1

O enunciado quer mostrar que, para quaisquer inteiros positivos m\ge2 e n\ge2, vale
R(m,n) \;=\; R(n,m),
onde R(m,n) é o menor inteiro N tal que, em qualquer coloração das arestas de K_{N} com duas cores (digamos vermelho e azul), aparece necessariamente um K_{m} todo vermelho ou um K_{n} 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
R(m,n)
é o mínimo inteiro N com a propriedade: em toda coloração das arestas de K_{N} em vermelho e azul surge ou um K_{m} monocor vermelho ou um K_{n} monocor azul. Em símbolos, para todo mapeamento
c\colon E(K_{N}) \to \{\text{vermelho},\,\text{azul}\}
existe um subgrafo completo de ordem m cujas arestas são todas vermelhas ou um subgrafo completo de ordem n cujas arestas são todas azuis.

Passo 3

Provar R(m,n)\le R(n,m). Seja N = R(n,m). Considere qualquer coloração
c\colon E(K_{N})\to\{\text{vermelho},\,\text{azul}\}.
Defina uma nova coloração
c'\colon E(K_{N})\to\{\text{vermelho},\,\text{azul}\}
trocando vermelho por azul e vice-versa em c. Como N=R(n,m), na coloração c' aparece ou um K_{n} todo vermelho (em c') ou um K_{m} todo azul (em c'). Mas isso significa, de volta em c, que ou existe um K_{n} todo azul ou um K_{m} todo vermelho. Logo N já satisfaz a propriedade de R(m,n), provando
R(m,n)\le N \;=\; R(n,m).

Passo 4

Provar R(n,m)\le R(m,n). Basta repetir o mesmo argumento trocando os papéis de (m,n) com (n,m). Tomando M=R(m,n) e aplicando a troca de cores, obtemos
R(n,m)\le M \;=\; R(m,n).

Passo 5

Das desigualdades
R(m,n)\le R(n,m) \quad\text{e}\quad R(n,m)\le R(m,n)
concluímos
R(m,n) \;=\; R(n,m).

Resposta

R(m,n) = R(n,m).

Exercícios relacionados