Uso de bases de Gröbner em Combinatória

Resumo: Vários problemas em Combinatória podem ter suas instâncias codificadas como conjuntos de vetores de naturais. Estes, por sua vez, podem ser codificados como polinômios, e às vezes ocorre que a estrutura do problema combinatório se reflete em estrutura algébrica da família de polinômios correspondente.

Frequentemente essa estrutura está presente no ideal gerado por esses polinômios, e os problemas originais podem ser traduzidos para problemas sobre ideais. Nessa altura, uma ferramenta básica para resolver quase tudo são bases de Gröbner. Algumas propriedades:

• Todo ideal tem uma base de Gröbner finita (pode ser grande).
• Existe um algoritmo que, dado um conjunto finito de polinômios computa uma base de Gröbner para o ideal que eles geram (pode demorar).
• Existem algoritmos eficientes que, dada um base de Gröbner de um ideal, resolvem problemas como pertinência, resolver o sistema de equações associado, e outros.

Nesse seminário serão apresentadas a teoria e algoritmos básicos, bem como algumas aplicações como solução de alguns problemas de programação inteira.

Os pré-requisitos em Álgebra são poucos (nem é preciso entender todos os termos usados acima).