Diferenças

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

--- grafos:ncromplano [2022/06/26 17:47] – edição externa 127.0.0.1
+++ grafos:ncromplano [2022/06/27 19:31] (atual) – edição externa 127.0.0.1
@@ Linha 7: / Linha 7: @@
 ===== 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)$.
+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)$.
 ----
@@ Linha 23: / 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 |}}
@@ Linha 33: / 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 43: / 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?400 |}}
+{{ :grafos:517.png?600 |}}