Applied Hilbert's Nullstellensatz for Combinatorial Problems

Algebraic Geometry;Combinatorial Optimization;Hilbert"s Nullstellensatz;Graph Coloring;Graph Theory

Romero Barbosa, Julian

University of Waterloo

关键词: Algebraic Geometry;    Combinatorial Optimization;    Hilbert";    s Nullstellensatz;    Graph Coloring;    Graph Theory;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/10897/3/Romero%20Barbosa_Julian.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Various feasibility problems in Combinatorial Optimization can be stated using systems of polynomial equations. Determining the existence of a extit{stable set} of a given size, finding the extit{chromatic number} of a graph or more generally, determining the feasibility of an extit{Integer Programming problem} are classical examples of this. In this thesis we study a powerful tool from Algebraic Geometry, called extit{Hilbert;;s Nullstellensatz}. It characterizes the extit{infeasibility} of a system of polynomial equations by the extit{feasibility} of a possibly very large system of extit{linear equations}. The solutions to this linear system provide extit{certificates}for the infeasibility of the polynomial system, called extit{Nullstellensatz Certificates}. In this thesis we focus on the study of Nullstellensatz Certificates for the existence of extit{proper colorings} of graphs. We use basic ideas from extit{duality theory} to determine various properties of the Nullstellensatz Certificates. We give new proofs to several known results in the current literature and present some new results that shed some light on the relationship between the sparsity of a graph and the extit{size} of the Nullstellensatz Certificates forextit{$k$-colorability}.