Sobre o número cromático do plano.

Com quantas cores podemos pintar o plano de maneira tal que pontos com a mesma cor não estejam a distância unitária?

Dado um conjunto $X$ e um número natural $r$, uma $r$-coloração é uma função $c: X \rightarrow \{1,\ldots ,r \} $. Dado $x \in X$, dizemos que $c(x)$ é a cor de $x$. Coloração é um dos conceitos mais importantes em combinatória, uma vez que diversos problemas podem ser expressados como um problema de colorações. Coloração em grafos, por exemplo, tem se destacado em aplicações práticas como escalonamento de tarefas e alocação de frequências. Neste post, estaremos interessados em colorir o plano (ou $\mathbb{R}^2$, se preferir).

Este é considerado por muitos matemáticos como um dos problemas mais difíceis em geometria plana (para um ensaio histórico sobre este problema e seus correlatos, indico o livro [1]). Quanto a sua origem, Erdös, por exemplo, disse uma vez "I cannot trace the origin of this problem", num artigo de 1961.

Bem, o problema já foi enunciado no início deste post, mas por educação, irei citá-lo mais uma vez:

Qual é o menor número de cores necessárias para colorir o plano de tal maneira que nenhum par de pontos de mesma cor estejam a distância unitária?

Este menor número de cores é o que chamamos de número cromático do plano, e denotamos por  $\chi(\mathbb{R}^2)$, ou somente por $\chi$.

Teorema de Turán.

Paul Turán (foto abaixo) foi um matemático húngaro especialista em teoria dos números e combinatória. Neste post, veremos um dos resultados que iniciou a teoria extremal dos grafos: o Teorema de Turán.

Seja $G$ um grafo simples com $n$ vértices. Qual é o maior números de aresta que $G$ pode ter de modo que não tenhamos em $G$ uma $p$-clique?

The Princeton Companion to Mathematics.

Este é o segundo post da série "livros que não só enfeitam a estante, mas que são matematicamente úteis (seja lá o que isso significa)".

Como dito num post anterior, a cada semana, irei indicar e comentar um livro que seja interessante para qualquer pessoa que usa matemática no seu dia-a-dia. Vamos ao segundo:

The Princeton Companion to Mathematics. Timothy Gowers, June Barrow-Green, Imre Leader.

Este livro de mais de 1000 páginas fala sobre quase tudo em matemática. Os problemas mais famosos e a áreas mais badaladas da matemática são descritas neste livro como uma daquelas enciclopédias que descrevem inúmeras coisas que você provavelmente não conhecerá por si só. 

Apesar de parecer uma enciclopédia matemática, este livro procura apresentar os tópicos numa sequência lógica. É claro que ele não é um livro para ser lido de pé-à-cabeça sequencialmente. É mais interessante você tê-lo como uma espécie de consultor. Qualquer assunto, atual ou não atual, tem um espaço reservado neste livro, desde que este assunto, em algum momento da história, tenha sido interessante.

Teorema da Recorrência de Poincaré.

Jules Henri Poincaré foi um dos mais brilhantes matemático do século XIX (e início do século XX). Considerado por muitos como o último universalista da matemática, devido a sua proeza de conseguir estudar "quase toda" área da matemática. Deixou inúmeros legados em diversas áreas tanto da matemática pura quanto da matemática aplicada.

O teorema que veremos neste post é um dos resultados clássicos em Teoria Ergódica conhecido como Teorema da Recorrência de Poincaré. Minha principal referência é o livro [1], mas indico o livro [2] para um aprofundamento na teoria. Indico também o texto [3] de Ricardo Mañé para algumas aplicações interessantes do teorema.

Considere um espaço de medida finita $(M,\Sigma, \mu)$. Dada uma aplicação mensurável $f:M\rightarrow M$, dizemos que $\mu$ é invariante pela aplicação $f$ se para todo $E\in \Sigma$ mensurável vale que

$$\mu(E) = \mu(f^{-1}(E)). $$

Dada uma propriedade sobre os elementos de $M$, por exemplo "beleza", dizemos que " $\mu$-quase todo" elementos de $M$ possuem esta propriedade quando o conjunto dos elementos que não possuem esta propriedade possuem medida nula, i.e., quando $\mu(\{x \in M: \text{ $x$ não é belo}\}) = 0$.

Vale ressaltar que dado $\{ E_k \}_{k\in \mathbb{N}}$ uma família enumerável de conjuntos mensuráveis disjuntos dois-a-dois, sendo $(M,\Sigma, \mu)$ um espaço de medida, temos que
$$ \mu \left( \bigcup_{k=1}^{\infty} E_k \right) = \sum_{k=1}^{\infty} \mu(E_k).$$


Com isso, já podemos enunciar e provar o 

Teorema (da Recorrência de Poincaré). Seja $f: M \rightarrow M$ uma transformação mensurável e $\mu$ uma medida invariante e finita. Seja $E\subseteq M$ qualquer conjunto mensurável com $\mu(E)>0$. Então, $\mu$-quase todo ponto $x\in E$ tem algum iterado $f^n (x)$, com $n\geq 1$, que também está em $E$.

Em outras palavras, o teorema afirma que quase todo ponto de $E$ regressa a $E$ no futuro. A prova deste teorema até que é simples.

Média aritmética-geométrica e a curva lemniscata.

Considere o seguinte problema que pode ser encontrado na maioria dos livros introdutórios de Análise Real: 

Seja $0 < a < b$ dois números reais. Defina as sequências $(a_n)_{n\in\mathbb{N}}$ e $(b_n)_{n\in\mathbb{N}}$ por $a_1 = a$, $b_1 = b$ e 

$$ a_{n+1} = \sqrt{a_n b_n} \quad \text{ e }\quad b_{n+1} = \frac{a_n + b_n}{2}, \quad (n = 1,2,3, \ldots).$$

Prove que estas duas sequências são convergentes e que elas convergem para o mesmo valor.

Este limite comum é o que chamamos de média aritmética-geométrica de $a$ e $b$ e é denotado por $M(a,b)$. Dados $a$ e $b$ quaisquer, em geral, não é fácil calcular $M(a,b)$. Em 30 de Maio de 1799, na idade de vinte e dois anos, Gauss (foto abaixo) escreveu em seu diário, que tinha verificado que a aproximação

$$\frac{1}{M(1,\sqrt{2})} \approx \frac{2}{\pi} \int_0^1 \frac{1}{\sqrt{1-t^4}} \;dt $$

é precisa, pelo menos até a décima primeira casa decimal.

Considere $\omega$ como o valor da integral na equação acima, i.e.,

$$\omega =  \int_0^1 \frac{1}{\sqrt{1-t^4}} \;dt.$$

Então, o que o Gauss conjecturou foi que 

$$ M(1,\sqrt{2}) = \frac{\pi}{2\omega}.$$

Aparentemente, fora o fato de envolver o $\pi$ e a $\sqrt{2}$, esta última equação não tem nada de mais. Mas ela esconde uma relação geométrica intrigante relacionada com duas curvas famosas.

Sobre uma identidade de Ramanujan.

O matemático indiano, Srinivasa Ramanujan (foto abaixo), propôs uma vez, no Journal of Indian Mathematical Society, o seguinte problema:

Determinar o valor de $$\sqrt{ 1 + 2\sqrt{ 1 + 3\sqrt{1 + 4\sqrt{ 1 + 5\sqrt{1 + \cdots}}}}}.$$

Ele esperou por seis meses que alguém lhe enviasse uma solução. Como ninguém enviou, ele publicou a sua própria solução [1].

Neste post, daremos uma prova analítica de que  $$\sqrt{ 1 + 2\sqrt{ 1 + 3\sqrt{1 + 4\sqrt{ 1 + 5\sqrt{1 + \cdots}}}}} = 3.$$

Um Guia de Estudante para o Estudo, Prática e Ferramentas de Matemática Moderna.

Este é um post da série "livros que não só enfeitam a estante, mas que são matematicamente úteis (seja lá o que isso significa)".

A cada semana, irei indicar e comentar um livro que seja interessante para qualquer pessoa que usa matemática no seu dia-a-dia. Vamos ao primeiro:

A Student's Guide to the Study, Practice and Tools of Modern Mathematics. Donald Bindner & Martin Erickson.

( Um Guia de Estudante para o Estudo, Prática e Ferramentas de Matemática Moderna.)

Este é um ótimo livro para quem está se engajando na matemática. Vale para alunos de matemática, de física, de engenharia e de qualquer outra área das Ciências Exatas.

Sobre o teorema de Ceva e o de Menelau.

Neste post, provarei dois teoremas importantes em geometria: o de Ceva e o de Menelau. Os dois teoremas  possuem similaridades, mas um fala de concorrência, enquanto o outro fala de colinearidade. 

Teorema de Ceva. Seja ABC um triângulo qualquer e D, E e F pontos sobre os lados BC, CA e BC, respectivamente. Os seguimentos AD, BE e CF são concorrentes se, e somente se, $$\frac{AF}{FB}\frac{BD}{DC}\frac{CE}{EA} = 1.$$

Pode GLOBALHELLFRY ser um número primo?

No livro Magic for Dummies contém a seguinte passagem:

Se você trocar cada uma das letras distintas de GLOBALHELLFRY por dígitos distintos e você obtiver um número primo, então o mundo irá sofrer uma terrível onda de calor. 

 É possível usar isto para criar uma onda de calor?

Nota: "Global hell fry" significa algo como "inferno global fritante", ou pelo menos assim tento traduzir.

Relação de Euler (prova combinatória)

Nos dois últimos posts, provamos a relação de Euler usando grafos e geometria elementar. Neste post, provaremos usando contagem dupla.

Teorema (da relação de Euler). Se $P$ é um poliedro convexo com $V$ vértices, $E$ arestas e $F$ faces, então vale que $$V-E+F = 2.$$

Demonstração. Primeiro "abra" o poliedro de modo que todas as faces esteja sobre um plano. Fazemos uma contagem dupla da soma S de todo os ângulos internos do poliedro resultante. Sejam $N_1,N_2,\ldots,N_F$ a quantidade de arestas (e de vértices) de cada uma das faces, sendo $N_1$ a da face que delimita todas as outras. Uma vez que a soma dos ângulos interno de um polígono de $n$ lado é $(n-2)\cdot 180º$, temos que

$$ S = (N_2-2) 180º + (N_3-2)180º + \cdots + (N_F-2)180º\\=(N_2 + N_3 + \cdots + N_F)180º - 2(F-1)180º. $$

Fazendo, agora, a contagem através dos vértices, temos que

$$ S = (V-N_1)360º + (N_1-2)180º.$$

Igualando as duas somas, obtemos que

$$ (N_2 + N_3 + \cdots + N_F)180º - 2(F-1)180º = (V-N_1)360º + (N_1-2)180º,$$

que é equivalente a

$$2V -  (N_1 + N_2 + \cdots + N_F) + 2F = 4$$

Observe que a soma $N_1 + N_2 + \cdots + N_F$ é igual a $2E$, pois cada aresta aparece em exatas duas faces distintas. Portanto, $V-E+F = 2$. Isto conclui a demonstração.