Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

--- grafos:ncromplano [2022/06/23 00:04] – edição externa 127.0.0.1
+++ grafos:ncromplano [2022/06/27 19:31] (atual) – edição externa 127.0.0.1
@@ Linha 4: / Linha 4: @@
 O número cromático do plano, denotado por $\chi(\mathbb{R}^2)$, é a quantidade mínima de cores suficientes para colorir o plano de modo que, para todo ponto de uma determinada cor, não exista nenhum ponto desta mesma cor a uma distância unitária dele. Noutras palavras, dados dois pontos a uma distância unitária, esses dois pontos têm cores distintas.
+===== Soluções parciais =====
+Até hoje não se sabe a resposta exata mas sabemos, com certeza, que $5\le\chi(\mathbb{R}^2)\le7$.
+A seguir, mostraremos como são encontradas essas limitações para $\chi(\mathbb{R}^2)$.
+----
+=== Limitantes Superiores ===
+Não é difícil apresentar quantidades de cores que são suficientes para colorir o plano de forma a satisfazer as regras do enunciado. O real desafio é encontrar o número **mínimo** de cores necessárias.
+A fim de encontrar um valor preciso para o número cromático, faz sentido que limitemos --- superior e inferiormente --- $\chi(\mathbb{R}^2)$. Para obter bons limitantes superiores basta que organizemos as cores de forma inteligente.
+A seguir mostraremos uma prova para $\chi(\mathbb{R}^2)\le9$ e, em seguida, para $\chi(\mathbb{R}^2)\le7$, que é o melhor limitante superior apresentado até o momento.
+Note que, se particionarmos o plano em quadrados iguais tais que a circunferência que os circunscreve tenha diâmetro $d:$ $\frac{\sqrt{2}}{2}<d<1$ ($\frac{\sqrt{2}}{2}\approx0,71$) e colorirmos de forma periódica cada bloco de 9 quadrados de forma que cada um deles possui uma cor diferente entre si, obtemos um plano "9-colorido" onde dado $x\in\mathbb{R}^2$ qualquer não há nenhum elemento $y$ de cor igual a $x$ tal que $\operatorname{d}(x,y)=1$. A seguir, vemos que o número cromático do plano é menor ou igual a 9.
+{{ :grafos:tilingpontos.png?300 |}}
+Seguindo esta mesma ideia, Hadwiger conseguiu mostrar que uma construção similar é possível com hexágonos regulares de diâmetro  $d:\underset{\underset{0,77}{\approx}}{\frac{4\sqrt{3}}{9}}<d<1$. Agora, notamos que o número cromático do plano é menor ou igual a 7 (construção de Hadwiger), como vemos abaixo.
+{{ :grafos:hextilingpontos.png?300 |}}
+----
+=== Limitantes Inferiores ===
+Para mostrar que $k$ é um limitante inferior, basta exibir um grafo no plano que não seja $(k-1)$-colorível.
+{{ :grafos:altmoser.png?300|}}
+Os primeiros casos são, de certa forma, triviais. A primeira prova mais sofisticada surge somente onze anos após a formulação do problema. Os irmãos Moser criaram o que ficou conhecido como //Moser spindle//, ilustrado ao lado.
+Quase sessenta anos depois da descoberta dos Moser, em 2018, um biólogo --- autoproclamado matemático amador --- faz um novo avanço no problema. Com assistência da programação, Aubrey de Grey começa a montar grafos com alta "densidade spindle" e os colorir com algorítmos computacionais.
+Em seu artigo, Aubrey encontra, inicialmente, um grafo com 20425 vértices que não é $4$-colorível. Com algumas técnicas de enxugamento ele obtém uma nova versão, agora com 1581 vértices.
+Os esforços de Aubrey foram de muita ajuda pois, em 2019, Marijn Heule usa os trabalhos do biólogo para gerar derivações dos grafos que também não são 4-coloríveis mas possuem menos vértices. O progresso mais recente de Heule foi de um grafo com apenas 510 vértices.
+Num período de menos de um ano, Jaan Parts refina ligeiramente o então menor grafo não 4-colorível. Novamente replicando as técnicas de de Grey, Parts consegue exibir um grafo com 509 vértices. Abaixo vemos o grafo de Heule com 517 vértices --- apenas para fins ilustrativos.
+{{ :grafos:517.png?600 |}}