Document details

Começamos com uma breve introdução ao polinômio cromático e de Tutte de grafos. Então damos uma introdução às álgebras de Hopf. Em combinátoria, álgebras de Hopf surgem visto que muitos objetos combinatórios tem associados a eles operações de união (levando a uma estrutura de multiplicação) e a decomposição (levando a uma estrutura de comultiplicação). Em seguida, discutimos alguns resultados clássicos de Tutte em V e W funções e polinômios de Tutte. Mostramos que o polinômio cromático é o único morfismo na categoria de álgebras de Hopf de uma álgebra de Hopf de grafos para uma álgebra de Hopf de polinômios, que é um resultado de Foissy. Emseguida, apresentamos um método algébrico de Hopf de Schmitt por sistemas de Whitney, demonstrando que o polinômio cromático de um grafo G pode ser determinado examinando apenas os subgrafos de G duplamente conexos, que é um resultado de Whitney. O último capítulo é sobre a conjectura de reconstrução de Ulam e Kelly. Aqui mostramos que certos argumentos de contagem usados por Kocay e Tutte são essencialmente idênticos a um argumento de contagem usado por Schmitt em seus métodos de álgebra de Hopf para o polinômio cromático.

We begin with a brief introduction to the chromatic and Tutte polynomial of graphs. We then give an introduction to Hopf algebras. In combinatorics, Hopf algebras arise since many combinatorial objects have associated with them operations of union (leading to multiplicative structure) and decomposition (leading to a comultiplicative structure). We then discuss some classic results of Tutte on V and W functions andTutte polynomials. We show that the chromatic polynomial is the unique morphism in the category of Hopf algebras from a Hopf algebra of graphs to a Hopf algebra of polynomials, which is a result of Foissy. We then present a Hopf algebraic method of Schmitt for Whitney systems, demonstrating that the chromatic polynomial of a graph G can be determined by examining only the doubly connected subgraphs of G, which is a result of Whitney. The last chapter is on the reconstruction conjecture of Ulam and Kelly. Here we show that certain counting argument used by Kocay and Tutte are essentially identical to a counting argument used by Schmitt in his Hopf algebra methods for the chromatic polynomial.