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$.



É claro que uma cor não é suficiente para pintar o plano. Nem mesmo duas cores, uma vez que dados dois pontos a distância unitária $x$ e $y$, com a cor de $x$ sendo 1 a cor de $y$ sendo 2, temos que todos os pontos no círculo de raio 1 centrado em $x$ devem receber a cor 2 e todos os pontos  no círculo de raio 1 centrado em $y$ devem receber a cor 1. Mas estes círculos se intersectam, nos forçando a usar pelo menos mais uma cor para colorir os pontos de interseção dos círculos. Então temos que

Proposição 1. $\chi(\mathbb{R}^2) \geq 3.$

Uma outra maneira de verificar que $\chi \geq 3$ é olhando para um triângulo equilátero de lado 1, uma vez que os vértices deste triângulo deverão ter cores distintas. De qualquer maneria, podemos fazer mais do que isso:

Proposição 2. $\chi(\mathbb{R}^2) \geq 4.$

A demonstração desta afirmação é devida aos irmãos Leo e William Moser. A prova é simples. Basta dar um conjunto de vértices que nos forcem a usar 4 cores para colorirmos o plano. Pois bem, aqui está:

Neste desenho (conhecido como spindles dos Moser -- clique aqui para saber o que é um spindle), todas as arestas possuem comprimento 1. Vamos tentar pintar os vértices com três cores: 1,2 e 3. Suponha que o vértice A recebe a cor 1. Então os vértices B e C devem receber cores distintas e diferente de 1, logo devemos usar as cores 2 e 3 para pintarmos os vértices B e C.  Mas isso força o vértice D receber a cor 1. Da mesma maneira, concluímos que o vértice G deve receber a cor 1. Então teremos dois vértices, D e G, a distância unitária e com a mesma cor. Logo não podemos pintar o plano com apenas 3 cores. $\square$

A figura acima, usada pra mostrar que precisamos de mais de 3 cores para pintarmos o plano, não é tão "tirada do bolso". De fato, podemos pensar da seguinte maneira: suponha que podemos pintar o plano com três cores. Dado um triângulo equilátero (de lado 1) ABC, já sabemos que estes três pontos devem receber cores distintas. Considere então um ponto A' diferente de A tal que, junto de B e C, formem um triângulo equilátero (de lado 1) , como na figura abaixo. Temos que A' deverá receber a mesma cor que A. Ainda mais, se rotacionarmos o losango ABA'C em torno do ponto A, aqueles pontos que farão o papel do A' estarão sobre um círculo e deverão todos receber a mesma cor que A. Mas neste círculo, claramente existe uma corda de comprimento 1, e portanto teremos dois pontos com a mesma cor e com distância unitária.

Bem, a priori, nada nos garante que podemos pintar o plano com um número finito de cores. Pra cada número finito de cores, poderíamos arranjar invariantes geométricos como o triângulo equilátero ou como a da figura acima, que nos garantissem que o número cromático não existe. Mas felizmente (ou não!) temos que

Proposição 3. $\chi(\mathbb{R}^2) \leq 9.$

A prova desta proposição é simples também. A ideia é construirmos uma coloração do plano com 9 cores tal que pontos de mesma cor não estejam a distância unitária. Vejamos como isto pode ser feito.

Demonstração. Cobrimos o plano com quadrados de lado $l$ (este $l$ será especificado mais a frente). Agora colorimos um quadrado com a cor 1 e colorimos todos os 8 quadrados adjacentes com as 8 cores restantes. Estes nove quadrados forma um quadrado $3l \times 3l$ que chamaremos de $S$. Translações de $S$ cobrem o plano e determina uma 9-coloração do plano todo (veja a figura abaixo).

Agora vejamos como podemos escolher $l$ de maneira tal que pontos a distância unitária não recebam a mesma cor. Na verdade, tudo que devemos evitar é que o maior seguimento dentro de um quadrado de lado $l$ (que é a diagonal e tem comprimento $l\sqrt{2}$) tenha comprimento menor que 1 e que dois quadrados (de lado $l$) distintos e de mesma cor estejam a distância maior do que 1. Uma vez que a menor distância entre dois quadrados (de lado $l$) distintos de mesma cor é $2l$ (que correspondem ao espaço entre dois quadrados), basta então escolhermos $l$ tal que $l\sqrt{2} < 1$ e $1 < 2l$. i.e.,

$$ \frac{1}{2} < l < \frac{1}{\sqrt{2}}.$$

Ora, podemos escolher $l = 2/3$ e teremos o que queríamos. $\square$

Bem, ao cobrirmos por quadrados, fomos capazes de obter uma 9-coloração do plano. É natural nos perguntarmos se alguma outra cobertura pode nos dar uma coloração melhor. E de fato, sim. O segredo é fazer como as abelhas: usar hexágonos!

Proposição 4. $\chi(\mathbb{R}^2) \leq 7.$

A prova desta proposição segue as mesmas linhas da Proposição 3.

Demonstração. Cobrimos o plano com hexágonos regulares de lado $l$ (novamente, o $l$ será especificado futuramente). Colorimos um hexágono com a cor 1 e os seus 6 vizinhos com as 6 cores restantes. A união destes sete hexágonos forma um polígono altamente simétrico de 18 lados o qual chamaremos de flor e denotaremos por $P$. Agora, translações de $P$ cobrem o plano e determinam uma 7-coloração do plano todo (veja a figura abaixo).

Agora, para determinarmos $l$, devemos assegurar que o maior segmento dentro de um hexágono de lado $l$ (que é aquele que vai de um vértice ao seu oposto e mede $2l$) tenha comprimento menor que 1 e que dois hexágonos (de lado $l$) e com a mesma cor estejam a distância maior que 1. Uma vez que a distância  $d$ entre os dois mais próximos hexágonos (de lado $l$) distintos e de mesma cor é 

$$d = \sqrt{\left(\frac{3l\sqrt{3}}{2}\right)^2 + \left(\frac{l}{2}\right)^2} = l\sqrt{7},$$

temos então que escolher um $l$ tal que $2l < 1$ e $l\sqrt{7}> 1$, que é equivalente a 

$$ \frac{1}{\sqrt{7}} < l < \frac{1}{2}.$$

Então, escolhemos $l = 2/5$ e isto já é suficiente. $\square$

É incrível como estas afirmações que são simples de serem provadas é o melhor que os matemáticos conseguiram afirmar até hoje sobre o valor de $\chi(\mathbb{R}^2)$! Ou seja, tudo que sabemos sobre tal número se resume no seguinte

Teorema 1. $4 \leq \chi(\mathbb{R}^2) \leq 7.$

Algo mais incrível aparece quando tentamos calcular o número cromático do plano racional, i.e., $\mathbb{Q}^2$. Como sabemos, $\mathbb{Q}^2$ é denso em $\mathbb{R}^2$. Então, é de se esperar que $\chi(\mathbb{Q}^2)$ seja próximo de $\chi(\mathbb{R}^2)$. Contudo,

Teorema 2. $\chi(\mathbb{Q}^2) = 2.$

A prova deste teorema é devida a Douglas R. Woodall. Ela é simples, contudo um pouco longa. Daremos apenas um esboço dela de maneira tal que o leitor não deverá ter dificuldade em verificar os detalhes.

Demonstração (esboço). Considere a relação $\sim$ sobre $\mathbb{Q}^2$ definida da seguinte maiera: $(r_1,r_2) \sim (q_1,q_2)$ se, e somente se, ambos os número racionais $r_1 -  q_1$ e $r_2 - q_2$  possuem denominador ímpar em relação a sua fração simplificada (números inteiros são considerados como $\frac{n}{1}$, isto inclui o 0). O leitor é convidado a verificar que $\sim$ é uma relação de equivalência.

A partição de $\mathbb{Q}^2$ induzida por $\sim$ possui uma propriedade importante: se a distância entre dois pontos de $\mathbb{Q}^2$ é 1, então estes dois pontos pertencem ao mesmo conjunto da partição, i.e., são equivalentes segundo $\sim$. Novamente, não tiramos o prazer do leitor em verificar isto.

Agora, observe que se colorirmos uma classe da partição, a outra pode ser colorida da mesma maneira, uma vez que uma classe pode ser obtida por outra através de uma translação. Então vamos colorir a classe que contém o ponto $(0,0)$. Esta classe consiste dos pontos $(r_1,r_2)$ nos quais os denominadores das suas frações simplificadas são ambos ímpares.

Pois bem, então colorimos com a cor 1 os pontos da forma $\left(\frac{i}{i}, \frac{i}{i}\right)$ e $\left(\frac{p}{i}, \frac{p}{i}\right)$, e colorimos com a cor 2 os pontos da forma $\left(\frac{p}{i}, \frac{i}{i}\right)$ e $\left(\frac{i}{i}, \frac{p}{i}\right)$, onde $i$ indica um número ímpar e $p$ indica um número par. Assim, dois pontos a distância unitária não terão a mesma cor. $\square$

Exercício. Prove o Teorema 2 destrinchando os detalhes do esboço da prova.

O que tudo indica é que determinar o número cromático do $\mathbb{Q}^n$ é mais fácil do que determinar o número cromático do $\mathbb{R}^n$. De fato, temos alguns resultados que indicam isto. Por exemplo, sabemos que $\chi(\mathbb{Q}^3) = 2$ e que   $\chi(\mathbb{Q}^4) = 4$. Mas ainda assim, não temos resultados completos:

Fato 1. Os seguintes limitantes inferiores são conhecidos:

Contudo, é um problema em aberto determinar o valor exato de $\chi(\mathbb{Q}^n)$, para $n\geq 5$. Uma extensão interessante é o seguinte problema em aberto:

Determinar o número cromático de $\mathbb{Q}^2[\sqrt{2}]$ e, em geral, de qualquer extensão algébrica de $\mathbb{Q}^2$.

O leitor que quiser saber mais sobre tais problemas pode consultar a referência [1].

Bem, isto é tudo por hoje! Até a próxima!

Referência.
[1] Alexander Soifer. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. Springer, 2009