Revendo os estudos sobre o Princípio de Dirichlet (Teorema da Casa de Pombos), encontrei uma relação deste com outro teorema, fundamentado sobre a temática dos grafos. Trata-se do Teorema de Ramsey.
Frank Plumpton Ramsey, nasceu em 1903, viveu pouco menos de 27 anos, foi filósofo, matemático e economista. Estudou no Trinity College (1915), em Cambridge, para estudar matemática, completando o ensino secundário em Winchester, em 1920. Tornou-se um estudante sênior em 1921 e graduou-se como um Wrangler no Tripos Matemática de 1923. Em 1926, foi indicado a professor em matemática na Universidade de Cambridge, tornando-se posteriormente Diretor de Estudos de Matemática no King's College.
Frank foi acometido de um ataque de icterícia e faleceu em 1930. Apesar do pequeno período de vida contribui muito em vários campos; na matemática, é considerado responsável para o crescimento de uma nova área, que leva o nome 'teoria de Ramsey'. Uma de suas contribuições está relacionada à lógica (sobre grafos), aplicada mais abaixo com um de seus teoremas.
Frank foi acometido de um ataque de icterícia e faleceu em 1930. Apesar do pequeno período de vida contribui muito em vários campos; na matemática, é considerado responsável para o crescimento de uma nova área, que leva o nome 'teoria de Ramsey'. Uma de suas contribuições está relacionada à lógica (sobre grafos), aplicada mais abaixo com um de seus teoremas.
Exemplo
Em uma reunião, há $6$ pessoas. Mostre que necessariamente existem $3$ pessoas que se conhecem mutuamente ou $3$ pessoas que não se conhecem mutuamente (admita que se a pessoa $A$ conhece a pessoa $B$, então a pessoa $B$ conhece a pessoa $A$).
Solução: Usaremos o diagrama a seguir, ilustrando a situação. Cada pessoa é representada por um vértice do hexágono. Quando duas pessoas se conhecem, ligamos os vértices correspondentes por um segmento em vermelho; se elas não se conhecem, usamos um segmento em verde. O que devemos mostrar é que, nesta figura, necessariamente existe um triângulo formado por linhas vermelhas ou um triângulo formado por linhas verdes.
Consideremos os segmentos que incidem em um dos vértices $P1$. Como eles são $5$, há pelo menos $3$ deles que são vermelhos ou pelo menos $3$ que são verdes. Admitamos que haja $3$ vermelhos (o argumento no caso de serem verdes é análogo).
Denotemos por $P2$, $P3$ e $P4$ os vértices ligados a $P1$ por segmentos vermelhos. Se algum dos segmentos $P2P3$, $P2P4$ ou $P3P4$ é vermelho, este segmento, juntamente com os que ligam seus extremos a $P1$, formam um triângulo de lados em vermelho.
Por outro lado, se nenhum deles é vermelho, eles formam um triângulo de lados verdes, o que completa a demonstração.
Com isso, mostramos que existem pelo menos $3$ pessoas que se conhecem mutuamente ou $3$ pessoas que não se conhecem mutuamente.
Teorema de Ramsey
O exemplo anterior é parte do artigo "O Princípio das Gavetas", de Paulo Cezar Pinto Carvalho; tal exemplo é equivalente a: se tomamos $6$ pontos, e pintamos cada segmento que une dois desses pontos de vermelho ou verde, então necessariamente existe um triângulo cujos vértices são três destes pontos e cujos $3$ lados são da mesma cor. O exemplo apresentado é um caso particular de um teorema mais geral, chamado de Teorema de Ramsey.
Tal teorema trata da coloração de grafos. Um grafo é um conjunto finito de vértices ligados por arestas, de modo que:
Tal teorema trata da coloração de grafos. Um grafo é um conjunto finito de vértices ligados por arestas, de modo que:
- não haja laços, isto é, um vértice nunca está ligado a si mesmo por uma aresta, e
- não haja arestas múltiplas, isto é, um mesmo par de vértices está ligado por no máximo uma aresta.
Enuncia-se (Teorema de Ramsey para hipergrafos):
Sejam $r$, $k\ge 1$. Para qualquer coloração $c:\left( \begin{matrix} N \\ k \end{matrix} \right) \rightarrow \left[ r \right] $ das arestas do hipergrafo $G=\left(N ,\left( \begin{matrix} N \\ k \end{matrix} \right) \right) $ , existe pelo menos uma cor $i\in \left[ r \right]$ e um subconjunto $A\subset N$ tal que $\left| A \right| =\infty$ e para todo $\left\{ { a }_{ 1 },...,{ a }_{ k } \right\} \subset A$ de cardinalidade $k$ temos $c\left( \left\{ { a }_{ 1 },...,{ a }_{ k } \right\} \right) =i$.
Há outra versão para o teorema encontrada na referência [1], página 13, constando da devida demonstração.
Referências
[1] CERIOLI, Marcia R. FREITAS, Renata de. Princípio da Casa dos Pombos. Disponível em: http://www.uff.br/grupodelogica/textos/principio_das_casas_de_pombo.pdf, acesso em 28 jun. 2014.
[2] Math.Info. Frank Ramsey. Artigo traduzido e disponível em: http://www.learn-math.info/portugal/historyDetail.htm?id=Ramsey, acesso em 26 jun. 2014.
[2] Math.Info. Frank Ramsey. Artigo traduzido e disponível em: http://www.learn-math.info/portugal/historyDetail.htm?id=Ramsey
[4] PUC-Rio. O Teorema de Ramsey. Disponível em <http://www.maxwell.lambda.ele.puc-rio.br/13399/13399_4.PDF>, acesso em 26 jun. 2014.
[5] Wikipedia. Frank P. Ramsey. Disponível em: http://en.wikipedia.org/wiki/Frank_ P._Ramsey, acesso em 28 jun. 2014.
Comente este artigo: