Ata da aula de 2002-11-18

MO405 - Atas das Aulas

Ata de Aula: 18/11/2002

Capitulo: 8.3.1 Ramsey Theory
Redator: Evandro Cesar Bracht 014860

Tópicos Discutidos mais importantes:

1 - Dentre 6 pessoas há 3 que mutuamente se conhecem ou há 3 que mutuamente não se conhecem

* Podemos mapear esta preposição para teoria dos grafos, onde um grupo de 6 pessoas pode ser representado por um grafo G de 6 vértices. E a afirmação de que "existe 3 pessoas que se conhecem mutuamente ou 3 pessoas que se desconhecem mutuamente" significa encontrar um triangulo em G ou no complemento de G.

* A prova desta preposição baseia-se no principio das casas de pombo. A soma dos graus de um vértice x em G e no complemento de G é igual a 5, entao pelo principio da casa de pombos implica que num deles, em G ou no complemento de G, x tem pelo menos grau 3. Por simetria, podemos assumir que o grau de x é maior ou igual a 3 em G. Se dois vizinhos de x são adjacentes, então eles formam um triangulo com x. Senao três vizinhos de x formam um triângulo no complemento de G.

2- Número de Ramsey R(p,q)

* O número de Ramsey N = R(p,q) indica o número de vértices necessário para que qualquer grafo com N vértices tenha um clique de tamanho p ou um conjunto independente de tamanho q.

2.1- Brincadeira de Erdos sobre o R(5,5) e R(6,6)
* Erdos fez uma brincadeira em relação a dificuldade de computar o número de Ramsey, que é a seguinte:

Se um alien ameaçar nos destrui e só não o fará se lhe diser o valor exato de R(5,5), então deveríamos pôr todos os computadores da terra a processar exaustivamente para encontrar o valor de R(5,5).
Já se o alien pedisse o R(6,6) Erdos nos aconselha a tentar matar o alien.

2.2- R(3,3)=6 e R(3,4)=9

* O valor o R(3,3)=6 já foi calculado e justificado em (1 - Dentre 6 pessoas há 3 que mutuamente se conhecem ou há 3 que mutuamente não se conhecem).

* Uma forma de se demonstrar que o valor de R(p,q) não pode ser um determinado N é simplesmente encontrar um grafo que não possui um clique de tamanho p e também não possui um conjunto independente de tamanho q. O valor de R(3,4) não pode ser 8 pelo grafo ao lado, onde ele não possui um K₃ e também não possui um conjunto independente de tamanho 4.

* Alem disso temos que um dado vértice x de G, nós podemos adicionar x a 2 vizinhos adjacentes para formar um triângulo ou adicionar x a um conjunto independente de tamanho 3 de não vizinhos para formar um conjunto independente de tamanho 4. Como R(2,4)=4 e R(3,3)=6, concluímos que se x tem 4 vizinhos ou 6 não vizinhos, então G tem um triângulo ou um conjunto independente de tamanho 4. Evitando ambos os limites, x deve ter no máximo 3 vizinhos e no máximo 5 não vizinhos, o que nos dá n(G)<=9. Se isto ocore em um grafo de 9 vértices, então todos os vértices devem ter exatamente 3 vizinhos. Desde que a fórmula da soma dos graus proíbe grafos 3-regulares com 9 vértices, nós obtemos R(3,4)=9.

2.3- R(p,q)<=R(p-1,q) + R(p,q-1) (Teorema 8.3.11 pg 385)

* Um ponto interessante neste teorema é que através dele podemos obter limites para o Número de Ramsey. Com base nestes limites podemos afirmar que sempre existe um N tal que um grafo com N vértices tem um clique de tamanho p ou um conjunto independente de tamanho q.

3- Bandwidth e complexidade de computá-la

* O Bandwidth B(G) de um grafo G é a menor dilatação de uma numeração de G.

* Quando os vértices de G são númerados com inteiros distintos, a Dilatação é a maior diferença entre inteiros associados a vértices adjacentes.

* Computar o Bandwidth de um grafo é um problema NP-completo mesmo para árvores de grau máaximo 3.