Independence Theory in Combinatorics: An Introductory Account with Applications to Graphs and Transversals es un libro de texto de matemáticas de nivel universitario sobre la teoría de matroides . Fue escrito por Victor Bryant y Hazel Perfect , y publicado en 1980 por Chapman & Hall.
Un tema principal de la Teoría de la Independencia en Combinatoria es la naturaleza unificadora de la abstracción y, en particular, la forma en que la teoría matroide puede unificar el concepto de independencia proveniente de diferentes áreas de las matemáticas. [1] Tiene cinco capítulos, el primero de los cuales proporciona definiciones básicas en teoría de grafos , combinatoria y álgebra lineal , y el segundo define e introduce matroides , llamados en este libro "espacios de independencia". [2] Como sugiere el nombre, estos se definen principalmente a través de sus conjuntos independientes, pero tienen equivalencias con definiciones que usan circuitos, rango matroide y función de conjunto submodular.también se presentan, al igual que sumas, menores, truncamientos y duales de matroides. [3]
El capítulo tres se refiere a las matroides gráficas , las matroides de árboles de expansión en grafos, [2] y el algoritmo codicioso para árboles de expansión mínimos . [3] El capítulo cuatro incluye material sobre matroides transversales , que pueden describirse en términos de coincidencias de grafos bipartitos , e incluye material adicional sobre teoría de coincidencias y temas relacionados, incluido el teorema del matrimonio de Hall, el teorema de Menger (una equivalencia entre cortes mínimos y conjuntos máximos disjuntos caminos en grafos), cuadrados latinos y gammoides .[2] [3] El último capítulo se refiere a las representaciones de matroides usando independencia lineal en espacios vectoriales , [2] etiquetado como un apéndice y presentado con menos pruebas. [1] [3] [4]
El nivel del texto es apropiado para cursos para estudiantes avanzados de pregrado o maestría, [1] con solo álgebra lineal básica como requisito previo, [2] [4] [5] y cubre su material a un nivel más accesible y general que otros textos sobre teoría matroide. [3] [4] [6] Aunque no está de acuerdo con la elección del libro de omitir el tema relacionado de las redes geométricas , el crítico Dominic Welsh lo llama "un texto ideal para un curso de pregrado sobre teoría combinatoria". [2] Michael J. Ganley lo llama de manera similar "una muy buena introducción a un tema bastante difícil". [4]
Sin embargo, el crítico W. Dörfler se queja de que el libro tiene una cobertura inadecuada de las aplicaciones prácticas y le falta una bibliografía adecuada. [3] Otra queja, de Bernhard Korte , es que el título del libro es engañoso: "espacios de independencia" a menudo se refiere de manera más general a complejos simpliciales abstractos , mientras que el libro se concentra mucho más específicamente en matroides. Korte también se hace eco de las quejas de los otros revisores sobre la falta de cobertura de las aplicaciones en la optimización combinatoria y de las conexiones con la teoría de redes. [5]