<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T21:03:43Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/10897" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/10897</identifier><datestamp>2025-03-26T23:37:38Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9928</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Tunçel, Levent</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="b59bcdbb-a4f4-436d-a5ad-ac6b7f80f9da" confidence="600">Romero Barbosa, Julian</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2016-09-23T18:27:42Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2016-09-23T18:27:42Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2016-09-23</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2016-09-13</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/10897</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">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&amp;apos;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}. &#xd;
&#xd;
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}.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Algebraic Geometry</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Combinatorial Optimization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Hilbert&amp;apos;s Nullstellensatz</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Graph Coloring</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Graph Theory</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Applied Hilbert&amp;apos;s Nullstellensatz for Combinatorial Problems</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Tunçel, Levent</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>