[obm-l] Mais Ramsey

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Oi, pessoal:

Aqueles problemas dos 6 matematicos / 2 temas ou 17 matematicos / 3 temas,
etc. sao casos particulares do teorema de Ramsey (vide artigo do Gugu na
Eureka no. 6)

Estes problemas podem ser expressos de forma mais sucinta com a linguagem de
grafos. Muito informalmente, um grafo pode ser representado por um conjunto
de pontos num plano (vertices) e linhas ligando pares desses pontos
(arestas). Se duas arestas se cruzarem (e em certos casos isso eh
inevitavel), o ponto de interseccao nao eh contado como vertice.

Um grafo completo de ordem n consiste de n vertices e das Binom(n,2) =
n(n-1)/2 arestas ligando cada par de vertices.

Um subgrafo de um dado grafo consiste de um subconjunto dos vertices do
grafo e de todas as arestas (e somente estas) pertencentes ao grafo e que
ligam dois vertices quaisquer desse subconjunto.

Agora, o problema dos 6 matematicos / 2 temas pode ser reformulado da
seguinte forma: Prove que se pintarmos cada aresta de um grafo completo de
ordem 6 com uma dentre duas cores, este grafo conterah um subgrafo
monocromatico de ordem 3 (um triangulo, por assim dizer).

O dos 17 matematicos / 3 temas fica: Prove que se pintarmos cada aresta de
um grafo completo de ordem 17 com uma dentre tres cores, este grafo conterah
um triangulo monocromatico.

A mensagem anterior do Nicolau generalizou este problema aumentando o numero
de cores. Dado um numero de cores, o problema eh achar o menor numero de
vertices que forca a existencia de um triangulo monocromatico. Repare que,
mesmo para um caso relativamente pequeno como 4 cores, o maximo que se sabe
eh que o numero minimo de vertices eh maior do que 50 e menor do que 63.
Essa situacao de ignorancia eh tipica da teoria de Ramsey (de novo, veja o
artigo do Gugu para ter uma ideia do quao pouco se sabe).

***

Uma outra forma de se generalizar o problema eh mantendo o numero de cores
fixo em 2 mas exigindo-se a presenca de um subgrafo monocromatico completo
de ordem maior do que 3.

Chamando as cores de azul e vermelho, o menor numero de vertices necessario
para garantir a presenca de um subgrafo completo azul de ordem m ou de um
subgrafo completo vermelho de ordem n eh denotado por R(m,n).

Por exemplo, sabe-se que R(3,3) = 6 (esse eh o caso dos 6 professores / 2
temas), R(3,4) = R(4,3) = 9 e que R(4,4) = 18. Um bom exercicio eh provar
que R(4,4) <= 18. Provar a igualdade eh mais dificil. Uma forma eh exibindo
um grafo completo de ordem 17, em que cada aresta eh pintada com uma dentre
duas cores, e que nao contenha nenhum subgrafo monocromatico completo de
ordem 4.


Um abraco,
Claudio.

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================