Back to search

University of Waterloo

Applied Hilbert's Nullstellensatz for Combinatorial Problems

Abstract

dc:description.abstract

Various feasibility problems in Combinatorial Optimization can be stated using systems of polynomial equations. Determining the existence of a \textit{stable set} of a given size, finding the \textit{chromatic number} of a graph or more generally, determining the feasibility of an \textit{Integer Programming problem} are classical examples of this. In this thesis we study a powerful tool from Algebraic Geometry, called \textit{Hilbert's Nullstellensatz}. It characterizes the \textit{infeasibility} of a system of polynomial equations by the \textit{feasibility} of a possibly very large system of \textit{linear equations}. The solutions to this linear system provide \textit{certificates} for the infeasibility of the polynomial system, called \textit{Nullstellensatz Certificates}. In this thesis we focus on the study of Nullstellensatz Certificates for the existence of \textit{proper colorings} of graphs. We use basic ideas from \textit{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 \textit{size} of the Nullstellensatz Certificates for \textit{$k$-colorability}.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2016

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Romero Barbosa, Julian
Advisor dc:contributor.advisor
  • Tunçel, Levent

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/10897

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Romero Barbosa, Julian. Applied Hilbert's Nullstellensatz for Combinatorial Problems. University of Waterloo, 2016. http://hdl.handle.net/10012/10897