Aurichi Aula 1

Prévia do material em texto

1 Ramsey
Problema 1.1. Numa festa com 6 pessoas, e´
verdade que da´ para garantir que ha´ 3 pessoas
que se conhecem ou 3 que na˜o se conhecem?
Resolvendo: escolha uma pessoa qualquer da
festa. Com relac¸a˜o a`s outras pessoas, ou essa
pessoa conhece (pelo menos) 3 das outras, ou
na˜o conhece (pelo menos) 3. Suponha o primeiro
caso e olhe atentamente o desenho abaixo (a pes-
soa escolhida e´ representada pela bolinha mais no
alto).
Problema 1.2. Daria para fazer o mesmo com
5 pessoas?
Problema 1.3. E se em vez de procurar por 3
pessoas, procura´ssemos 4 pessoas (que se conhe-
cem ou na˜o se conhecem entre si)?
Pode-se mostrar que numa festa com 18 pes-
soas isso e´ sempre poss´ıvel. Mais legal, pode-se
mostrar que esse e´ o menor tamanho para uma
festa ter para sempre se garantir essa proprie-
dade.
Problema 1.4. E se troca´ssemos para 5, 6 etc?
Sempre existe um tamanho de festa que satisfac¸a
isso?
Teorema 1.5 (de Ramsey, versa˜o finita). Dado
p > 0, existe N ∈ N tal que para toda bicolorac¸a˜o
sobre as arestas de KN , existe um Kp ⊂ KN
monocroma´tico1.
1Aqui vamos provar com apenas duas cores, mas da´
para fazer para qualquer quantidade finita de cores. Tente
em casa.
Voceˆ pode tentar uma demonstrac¸a˜o direta
para o resultado acima. Vamos tentar um ca-
minho indireto e infinito.
Teorema 1.6 (de Ramsey, versa˜o infinita).
Dado um grafo infinito completo e uma bico-
lorac¸a˜o sobre suas arestas, existe um subgrafo in-
finito completo e monocroma´tico2.
Demonstrac¸a˜o. Vaoms fazer o caso em que os
ve´rtices sa˜o os pontos de N. Considere a1 = 1.
Note que existe uma cor c1 tal que H1 = {n >
a1 : {a1, n} tem cor c1} seja infinito. Seja a2 ∈
H1. Note que existe c2 tal que H2 = {n ∈ H1 :
{a1, a2} tem cor c2} e´ infinito. Defina a3 ∈ H2 e
c3 de forma que H3 = {n ∈ H2 : {a2, a3} tem cor
c3} seja infinito e continue. Note que existe uma
cor c tal que c = ck para infinitos k’s. Note que
H = {an : cn = k} e´ o conjunto desejado3.
Como aplicac¸a˜o do u´ltimo resultado, vejamos
que podemos usa´-lo para provar o seguinte resul-
tado:
Teorema 1.7. Toda sequeˆncia (xn)n∈N de
nu´meros reais distintos admite subsequeˆncia
crescente ou admite subsequeˆncia decrescente4.
Demonstrac¸a˜o. Considere o grafo completo cu-
jos ve´rtices sa˜o os xn’s. A aresta {xj , xk} e´ co-
lorida de C se esses dois termos aparecem na or-
dem crescente na sequeˆncia e de D caso contra´rio.
Aplique Ramsey e pense no que aconteceu.
Vamos ver como usar a versa˜o infinita de Ram-
sey para provar a versa˜o finita. O seguinte resul-
tado e´ u´til para isso:
Teorema 1.8 (de Ko¨nig). Se T e´ uma a´rvore
infinita que bifurca finitamente, enta˜o T admite
um ramo infinito.
E´ importante notar que a hipo´tese do “bifurcar
finitamente” e´ necessa´ria.
Como se usa tal resultado para provar o Ram-
sey finito? Suponha que na˜o vale o Ramsey fi-
nito. Enta˜o existe p tal que para todo N , existe
2Aqui novamente apresentamos com apenas duas cores,
mas o resultado continua valendo para qualquer quanti-
dade finita de cores.
3Um desenho da construc¸a˜o ajuda!
4Estamos supondo as subsequeˆncias infinitas.
uma bicolorac¸a˜o em KN tal que na˜o existe Kp
monocroma´tico. Considere a a´rvore de todas
as bicolorac¸o˜es poss´ıveis em KN ’s (coloque ares-
tas quando uma colorac¸a˜o estende a outra). O
ramo dado por Ko¨nig da´ um grafo infinito sem
subgrafo completo monocroma´tico (na˜o tem nem
Kp), o que e´ uma contradic¸a˜o com o Ramsey in-
finito.
Apesar de sabermos que dado qualquer p,
existe N , na˜o sabemos como calcular tal N . Pro-
vamos que R(3) = 6 e comentamos que R(4) =
18. Mas a u´nica coisa que se sabe sobre R(5) e´
que 43 ≤ R(5) ≤ 48. Sobre R(6), sabemos que
102 ≤ R(6) ≤ 165.
Ja´ que apresentamos o resultado sobre
sequeˆncias, vamos apresentar uma versa˜o finita
do mesmo.
Teorema 1.9 (Erdo˝s / Szekeres). Sejam m,n ∈
N. Enta˜o, dada uma sequeˆncia com mn + 1
nu´meros reais distintos, existe uma subsequeˆncia
crescente com m+1 nu´meros ou existe uma sub-
sequeˆncia decrescente com n + 1 nu´meros.
Demonstrac¸a˜o. Considere x1x2 · · ·xmn+1 uma
sequeˆncia como no enunciado. Para cada i =
1, ...,mn + 1, seja ai a quantidade de elemen-
tos da maior sequeˆncia crescente comec¸ando em
xi. Seja bi a quantidade de elementos da maior
sequeˆncia descrescente terminando em xi. Note
que se algum i e´ tal que ai ≥ m + 1 ou algum
bi ≥ n + 1, terminamos.
Ou seja, so´ precisamos mostrar que o caso em
que ai ≤ m e bi ≤ n para todo i e´ imposs´ıvel.
Note que temos uma func¸a˜o f(i) = (ai, bi). E,
que no caso em que estamos, f : {1, ...,mn+1} →
{1, ...,m} × {1, ..., n}. Note que
|{1, ...,m} × {1, ..., n}| = mn
Assim, pelo princ´ıpio da casa dos pombos, f na˜o
e´ injetora. Ou seja, existem i1 e i2 tais que 1 ≤
i1 < i2 ≤ mn + 1 tais que (ai1 , bi1) = (ai2 , bi2).
Como xi1 6= xi2 , temos dois casos:
• xi1 < xi2 : Neste caso, qualquer sequeˆncia
crescente comec¸ando em xi2 pode ser esten-
dida para uma comec¸ando em xi1 . Logo,
ai1 > ai2 .
• xi1 > xi2 : Neste caso, qualquer sequeˆncia
decrescente terminando em xi1 pode ser es-
tendida para uma terminando em xi2 . Logo,
bi1 < bi2 .
Em ambos os casos, temos que (ai1 , bi1) 6=
(ai2 , bi2), contradic¸a˜o.
Para mais detalhes, procure em