Estudo sobre ideais, Bases de Gröbner e suas aplicações

Abstract

Neste trabalho, estudaremos o Teorema das Quatro Cores, problema que, apesar de simples de enunciar, ficou por mais de um século sem uma prova concreta. O resultado foi conjecturado em 1852, quando um matemático sul-africano chamado Francis Guthrie, ao tentar colorir o mapa de condados ingleses, notou que quatro cores bastavam para colorir cada região de modo que cada uma recebesse uma única cor e que condados vizinhos não fossem pintados com cores iguais. Daí, esta conjectura foi passando de boca em boca até chegar em Alfred Bray Kempe, que, em 1879, foi o primeiro a publicar uma tentativa de demonstração do Teorema, cujo método utilizado ficou conhecido como Método das Cadeias de Kempe. Porém, anos depois, em 1890, o matemático britânico Percy J. Heawood construiu um mapa no qual o processo de Kempe não funcionava, deixando a demonstração da até então Conjectura das Quatro Cores em aberto. Em 1976, 86 anos depois, foi publicado por Appel e Haken, finalmente, uma solução para o problema, com um detalhe curioso: eles tiveram o auxílio de um computador chamado IBM 360, que teve que realizar bilhões de cálculos por volta de 1200 horas. Em 1994, outro grupo de matemáticos conseguiu uma solução mais simples, também usando métodos computacionais, mas que ainda deixavam dúvidas pela dificuldade de ser analisada. Por fim, estas dúvidas foram saciadas por volta de 2005, graças ao trabalho de Georges Gonthier. Nosso papel aqui será fazer uma abordagem diferente sobre o Problema das Quatro Cores sem usar, ao menos explicitamente, Teoria dos Grafos, que seria a abordagem mais usual para lidar com regiões e adjacências. Usaremos, no lugar, o conhecimento obtido estudando Álgebra, mais especificamente sobre Anéis, Ideais de Polinômios e Bases de Gröbner, chegando a um algoritmo que apesar de não poder ser usado em geral por sua complexidade e custo computacional, tem muito valor teórico e é capaz de colorir, usando apenas ferramentas algébricas, cálculos simples e um pouco de inteligência, um mapa plano com no máximo quatro cores, como demonstrado pela literatura.