Combinatorial Nullstellensatz: Con aplicaciones a la coloración de grafos

Título original:

Combinatorial Nullstellensatz: With Applications to Graph Colouring

Contenido del libro:

Combinatorial Nullstellensatz es un teorema novedoso en álgebra introducido por Noga Alon para abordar problemas combinatorios en diversas áreas de las matemáticas. Este libro se centra en las aplicaciones de este teorema a la coloración de grafos. Un paso clave en las aplicaciones de Combinatorial Nullstellensatz es demostrar que el coeficiente de un determinado monomio en la expansión de un polinomio es distinto de cero. La mayor parte del libro se centra en tres métodos para calcular los coeficientes:

⬤ Orientación de Alon-Tarsi: La tarea consiste en demostrar que un grafo tiene una orientación con un grado de salida máximo dado y para el cual el número de subdigrafías eulerianas pares es diferente del número de subdigrafías eulerianas impares. En particular, este método se utiliza para demostrar que un grafo cuyo conjunto de aristas se descompone en un ciclo de Hamilton y triángulos separados por vértices es 3-elegible, y que todo grafo plano tiene una correspondencia cuya eliminación da como resultado un grafo 4-elegible.

⬤ Fórmula de interpolación para el coeficiente: Este método se utiliza, en particular, para demostrar que las rejillas toroidales de orden par son 3-elegibles, los grafos planares r-regulares coloreables son r-elegibles, y los grafos completos de orden p+1, donde p es un primo, son p-elegibles.

⬤ Coeficientes como permanentes de matrices: Este método se utiliza en particular en el estudio de la versión de lista de la ponderación vértice-borde y para demostrar que todo gráfico es (2,3)-elegible.

Es un libro de referencia adecuado para un curso de posgrado en matemáticas.