Diferenças

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

--- grafos:ncromplano [2022/06/26 17:44] – felipe
+++ grafos:ncromplano [2022/06/27 19:31] (atual) – edição externa 127.0.0.1
@@ Linha 6: / Linha 6: @@
 ===== 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 ===
@@ Linha 19: / Linha 25: @@
 {{ :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).
+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 ===
@@ Linha 27: / Linha 35: @@
 Para mostrar que $k$ é um limitante inferior, basta exibir um grafo no plano que não seja $(k-1)$-colorível.
-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//.
+{{ :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.
-{{ :grafos:altmoser.png?300 |}}
 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.
@@ Linha 37: / Linha 47: @@
 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.
+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 |}}