Algebraic methods for discrete problems

En esta tesis estudiamos tres problemas que relacionan Teoría de Grafos y Álgebra. En particular, consideramos el problema de contar el número de conjuntos independientes en un grafo, así como el problema relacionado de contar el número de anticadenas en un conjunto parcialmente ordenado, desde la perspectiva del álgebra computacional. También describimos los conjuntos independientes máximos de los grafos de de Bruijn B(d; 3), vía el estudio de la acción del grupo simétrico en d elementos. Además, determinamos todos los etiquetamientos aditivos de aristas y de vértices módulo d en un grafo, por medio de una traducción combinatoria de los correspondientes problemas de álgebra lineal sobre el anillo de enteros módulo d.In this thesis we study three problems that link Graph Theory and Algebra. In particular, we consider the problem of counting independent sets in a graph, as well as the related problem of counting antichains in a finite partially ordered set, from the perspective of computational algebra. We also completely describe the maximum independent sets of the de Bruijn graphs B(d; 3), via the study of the action of the symmetric group on d elements. Moreover, we determine all additive edge and vertex labelings modulo d on a graph, by combinatorially translating the corresponding linear algebra problems over the ring of integers modulo d.Fil:Tobis, Enrique Augusto. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina