% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.6}{23(1)}{2016} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} \usepackage{tikz} \usepackage{tikz} %\usetikzlibrary{arrows} %\usepackage{amstext} \usepackage{mathrsfs} %\usepackage{psfrag} \usepackage{url} %\usepackage{multirow} %\usepackage{latexsym} \usepackage{colordvi} \usepackage{bbm} \usepackage{color} %\usepackage[left=1in,top=1in,right=1in]{geometry} \usepackage{verbatim} \usepackage{xspace} \usepackage[plain]{fancyref} \usepackage{placeins} \usepackage{breqn} \usepackage{xstring} \usepackage{enumerate} %\usepackage{natbib} \usepackage{tkz-graph} \usepackage[labelfont=normalfont]{caption} \usepackage{subcaption} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \newcommand{\cone}{\mathbf{cone}} \newcommand{\fm}{{\mathfrak m}} \newcommand{\R}{{\mathbb R}} \renewcommand{\k}{\mathbbm{k}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \newcommand{\G}{\mathbb{G}} \newcommand{\C}{\mathbb{C}} \newcommand{\F}{\mathbb{F}} \newcommand{\PP}{\mathbb{P}} \newcommand{\rx}{\mathbb{R}[x_1,\ldots,x_n]} \newcommand{\gen}[1]{\langle #1 \rangle_{\F_2}} \newcommand{\FC}{{\overline{\mathbb{F}}}} \newcommand{\kS}{\k^\infty} \newcommand{\kD}{\kc^*} \newcommand{\Q}{\mathbb{Q}} \newcommand{\V}[1]{V_\kc(#1)} \newcommand{\W}{\mathcal{W}} \newcommand{\M}{\mathcal{M}} \newcommand{\x}{{\bf x}} \newcommand{\RD}{{R^*}} \newcommand{\codim}[2]{dim(#1/#2)} \newcommand{\Var}[2]{{\mathcal{V}_{#1}(#2)}} \newcommand{\norm}[1]{\left\Vert#1\right\Vert} \newcommand{\abs}[1]{\left\vert#1\right\vert} \newcommand{\set}[1]{\left\{#1\right\}} \newcommand{\Real}{\mathbb R} \newcommand{\eps}{\varepsilon} \newcommand{\To}{\longrightarrow} \newcommand{\BX}{\mathbf{B}(X)} \newcommand{\A}{\mathcal{A}} \renewcommand{\(}{\left(} \renewcommand{\)}{\right)} \renewcommand{\iff}{if and only if\xspace} \newcommand{\<}{\langle} \renewcommand{\>}{\rangle} \newcommand{\genR}[1]{\langle #1 \rangle_R} \newcommand{\genK}[1]{\langle #1 \rangle_\k} \newcommand{\ZZ}[1]{\mathbb{Z}/#1\mathbb{Z}} \renewcommand{\k}{\mathbbm{k}} \newcommand{\kc}{{\overline{\k}}} \newcommand{\linearspan}[1]{{\langle #1 \rangle}_{\mathbbm{k}}} \newcommand*\samethanks[1][\value{footnote}]{\footnotemark[#1]} % shortcuts \newcommand{\nulla}{\ifmmode{N_{\k}}\else N_{\k}\xspace\fi} \newcommand{\commasplit}[1]{\StrSubstitute{#1}{),(}{),\penalty0(}[\temp]\StrSubstitute{\temp}{\},\{}{\},\penalty0\{}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins %\renewenvironment{comment}{}{} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{problemma}[theorem]{Problemma} \newtheorem{problem}[theorem]{Problem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{example}[theorem]{Example} \newtheorem{case}{Case} \newtheorem{subcase}{Case} \newtheorem{subcases}{Case} \numberwithin{subcase}{case} \numberwithin{subcases}{subcase} %\newtheorem{casess}{Case} %\newtheorem{subcasess}{Case} %\newtheorem{subcasesss}{Case} %\numberwithin{subcasess}{casess} %\numberwithin{subcasesss}{subcasess} % fancyref definitions \newcommand*{\fancyrefthmlabelprefix}{thm} \frefformat{plain}{\fancyrefthmlabelprefix}{theorem\fancyrefdefaultspacing#1} \Frefformat{plain}{\fancyrefthmlabelprefix}{Theorem\fancyrefdefaultspacing#1} \newcommand*{\fancyreflemlabelprefix}{lem} \frefformat{plain}{\fancyreflemlabelprefix}{lemma\fancyrefdefaultspacing#1} \Frefformat{plain}{\fancyreflemlabelprefix}{Lemma\fancyrefdefaultspacing#1} \frefformat{plain}{\fancyrefeqlabelprefix}{(#1)} \Frefformat{plain}{\fancyrefeqlabelprefix}{Equation\fancyrefdefaultspacing#1} \newcommand*{\fancyrefproplabelprefix}{prop} \frefformat{plain}{\fancyrefproplabelprefix}{proposition\fancyrefdefaultspacing#1} \Frefformat{plain}{\fancyrefproplabelprefix}{Proposition\fancyrefdefaultspacing#1} \newcommand*{\fancyrefdeflabelprefix}{def} \frefformat{plain}{\fancyrefdeflabelprefix}{definition\fancyrefdefaultspacing#1} \Frefformat{plain}{\fancyrefdeflabelprefix}{Definition\fancyrefdefaultspacing#1} \newcommand*{\fancyrefexlabelprefix}{ex} \frefformat{plain}{\fancyrefexlabelprefix}{example\fancyrefdefaultspacing#1} \Frefformat{plain}{\fancyrefexlabelprefix}{Example\fancyrefdefaultspacing#1} \Frefformat{plain}{\fancyreftablabelprefix}{Table\fancyrefdefaultspacing#1} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\Hom}{Hom} \DeclareMathOperator{\conv}{conv} % fix pmod spacing \makeatletter \let\@@pmod\pmod \DeclareRobustCommand{\pmod}{\@ifstar\@pmods\@@pmod} \def\@pmods#1{\mkern4mu({\operator@font mod}\mkern 6mu#1)} \makeatother \tikzstyle{vertex}=[circle, fill, inner sep=0pt, minimum size=5pt] \newcommand{\vertex}{\node[vertex]} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Low degree Nullstellensatz certificates for 3-colorability} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Bo Li\thanks{Supported by the Department of Mathematics at Harvey Mudd College.} \qquad Benjamin Lowenstein\samethanks \qquad Mohamed Omar \\ \small Department of Mathematics\\[-0.8ex] \small Harvey Mudd College\\[-0.8ex] \small Claremont, CA, U.S.A.\\ \small\tt \{bli,blowenstein,omar\}@g.hmc.edu } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Mar 17, 2015}{Dec 31, 2015}{Jan 11, 2016}\\ \small Mathematics Subject Classifications: 05C15, 05C50, 68W30} %%%%%%%%%%%% \begin{document} \maketitle \begin{abstract} In a seminal paper, De Loera et. al introduce the algorithm NulLA (Nullstellensatz Linear Algebra) and use it to measure the difficulty of determining if a graph is not 3-colorable. The crux of this relies on a correspondence between 3-colorings of a graph and solutions to a certain system of polynomial equations over a field $\k$. In this article, we give a new direct combinatorial characterization of graphs that can be determined to be non-3-colorable in the first iteration of this algorithm when $\k=GF(2)$. This greatly simplifies the work of De Loera et. al, as we express the combinatorial characterization directly in terms of the graphs themselves without introducing superfluous directed graphs. Furthermore, for all graphs on at most $12$ vertices, we determine at which iteration NulLA detects a graph is not 3-colorable when $\k=GF(2)$. \end{abstract} \section{Introduction}% In recent years, combinatorial optimization has flourished from algorithms that fundamentally rely on tools from algebraic geometry and commutative algebra. Work of Lasserre \cite{Lasserre2000}, Lov\'{a}sz-Schrijver \cite{LovaszSchrijver1991}, Sherali-Adams \cite{SheraliAdams1990}, Gouveia, Parrilo and Thomas \cite{GouveiaParriloThomas2008}, and many others have used polynomials to develop approximation algorithms for optimization problems. Another recent algorithm akin to those above is the Nullstellensatz Linear Algebra algorithm (NulLA) of De Loera et. al \cite{DeLoeraLeeMalkinMargulies08} which addresses feasibility issues in polynomial optimization. Given a set of polynomials $f_1,f_2,\ldots,f_s \in \k[x_1,\ldots,x_n]$ for some field $\k$, NulLA's goal is to certify that the system of equations $f_1=0, \ f_2=0, \ \ldots \ ,f_s=0$ has no solution in $\overline{\k}$, the algebraic closure of $\k$. It exploits Hilbert's Nullstellensatz, a celebrated and fundamental theorem in algebraic geometry (see \cite{CoxLittleOShea92}). \begin{theorem}[Hilbert's Nullstellensatz] Let\,$\k$\,be a field and $f_1,f_2,\ldots,f_s \in \k[x_1,\ldots,x_n]$. The system of polynomial equations \[f_1=0, \ f_2=0, \ \ldots, \ f_s=0\] has no solution in ${\overline{\k}}^n$ if and only if there are polynomials $\alpha_1,\alpha_2,\ldots,\alpha_s \in \k[x_1,\ldots,x_n]$ such that \[ 1=\alpha_1f_1 + \cdots + \alpha_sf_s. \] \end{theorem} The polynomials $\alpha_1,\alpha_2,\ldots,\alpha_s$ are referred to as a \emph{Nullstellensatz certificate} of infeasibility; indeed they are a witness that the polynomial system $f_1=0, f_2=0, \ldots, f_s=0$ has no solution. The maximum degree of the $\alpha_i's$ is referred to as the \emph{Nullstellensatz degree} of the system, and it is a measure of the complexity of certifying that the system of polynomial equations has no solutions. If a system of polynomial equations is known to have a Nullstellensatz certificate whose Nullstellensatz degree is a small constant (and if $\k$ is finite), one can find a Nullstellensatz certificate in polynomial time in the number of variables through a sequence of linear algebra computations (see \cite{DeLoeraLeeMalkinMargulies08} for details). However, for general polynomial systems, it is well known that the degree of Nullstellensatz certificates can grow as a function of the number of variables. The underlying paradigm in all the above algorithms is the construction of iterative approximations that are tractably computable at early stages. When applied to combinatorial optimization problems, particularly graph theoretic ones, the key problem that arises is determining the classes of graphs for which a given problem can be resolved in early iterations. For instance, when applied to the stable set problem, Gouveia, Parrilo and Thomas \cite{GouveiaParriloThomas2008} show that the first iteration of the theta body hierarchy solves the stable set problem for perfect graphs. This result was first established by Lov\'{a}sz \cite{Lovasz1994} by exploiting polynomials as well. NulLA itself was originally introduced as a means of unfolding classes of non-3-colorable graphs that can be detected to be non-3-colorable efficiently (that is, in polynomial time in the number of variables of a given graph). In particular, the authors of \cite{DeLoeraLeeMalkinMargulies08} applied the NulLA algorithm to the following algebraic formulation of graph 3-colorability due to Bayer. We will refer to this as Bayer's formulation throughout the manuscript. \begin{lemma}[Bayer \cite{Bayer82}] \label{bayer} A graph $G$ with vertex set $V$ and edge set $E$ is $3$-colorable if and only if the following system of equations has a solution over an algebraically closed field $\mathbbm{k}$ with $\mbox{char}(\mathbbm{k})$ relatively prime to $3$. \begin{align} &0=x_i^3-1& \forall i\in V& \label{eq:vpols} \\ &0=x_i^2+x_ix_j+x_j^2& \forall v_iv_j \in E& \end{align} \end{lemma} The fundamental concern then is determining combinatorial features of non-3-colorable graphs that dictate the minimum Nullstellensatz degree of infeasibility for the system in Lemma~\ref{bayer}, which we denote by $N_{\k}(G)$, is a small constant. In light of this, it is natural to address the following problem, a variant of which was first asked in \cite{Omar2010}: \begin{problem}\label{prob:nulla} Given a finite field $\k$, and positive integer $d$, characterize those graphs with $N_{\k}(G)=d$. \end{problem} Computational evidence (see, for example, Table 1 of \cite{DeLoera2015}) suggests that the minimum Nullstellensatz degree of a non-3-colorable under Bayer's formulation is smallest when the field of coefficients chosen is $GF(2)$ as opposed to $GF(p)$ for primes $p>2$, so from a computational complexity perspective, it may be beneficial to begin addressing Problem~\ref{prob:nulla} by working with Bayer's formulation when $\k=GF(2)$. A partial answer in this case was given by De Loera et. al \cite{Omar2010} (see their paper for relevant definitions). \begin{theorem}[Theorem 2.1 of \cite{Omar2010}] \label{thm:origcomb} For a given simple undirected graph $G$ with vertex set $V=\{v_1,v_2,\ldots,v_n\}$ and edge set $E$, the polynomial system over $GF(2)$ encoding the $3$-colorability of G \begin{equation*} J_G=\{x_i^3+1=0,\ x_i^2+x_ix_j+x_j^2=0:\ i\in V,\ v_iv_j\in E\} \end{equation*} has a degree one Nullstellensatz certificate of infeasibility if and only if there exists a set $C$ of oriented partial $3$-cycles and oriented chordless $4$-cycles from $\text{Arcs}(G)$ such that \begin{enumerate} \item $|C_{(v_i,v_j)}|+|C_{(v_j,v_i)}|\equiv0\pmod*2$ for all $v_iv_j\in E$ and \item $\sum_{(v_i,v_j)\in \text{Arcs}(G),ii,k$ is odd, and \item if $v_i,v_j \in V$ but $v_iv_j \notin E$, then the number of paths in $C$ with $v_i$ and $v_j$ as endpoints is even. \end{enumerate} \end{definition} \begin{example}\label{ex:wheel} Let $n$ be a positive integer. The graph $W_n$, referred to as the \emph{wheel} graph, is the graph whose vertex set is $\{v_1,v_2,\ldots,v_n,v_{n+1}\}$ where the induced subgraph on $V'=\{v_1,v_2,\ldots,v_n\}$ is a cycle and $v_{n+1}$ is a vertex adjacent to all vertices in $V'$. See \Fref{fig:wheelgraph} for an example. Without loss of generality, we may assume the cycle whose vertex set is $V'$ has edge set $\{v_1v_2,\ldots,v_{n-1}v_n,v_nv_1\}$. When $n$ is odd, the graph $W_n$ is covered by length 2 paths, as witnessed by the set $C=\{v_1v_{n+1}v_2,v_2v_{n+1}v_3,\ldots,v_{n-1}v_{n+1}v_n,v_nv_{n+1}v_1\}$. Indeed, this set satisfies all the conditions in Definition~\ref{def:deg1graphs}. \end{example} \begin{figure}[ht] \begin{center} \begin{tikzpicture}[scale=1.0] \vertex[label=right:$v_1$](v_1) at (0:1.8) {}; \vertex[label=above:$v_2$](v_2) at (72:1.8) {}; \vertex[label=left:$v_3$](v_3) at (144:1.8) {}; \vertex[label=below:$v_4$](v_4) at (216:1.8) {}; \vertex[label=right:$v_5$](v_5) at (288:1.8) {}; \vertex[label=left:$v_6$](v_6) at (0:0) {}; \path (v_1) edge (v_2) (v_2) edge (v_3) (v_3) edge (v_4) (v_4) edge (v_5) (v_5) edge (v_1) (v_6) edge (v_1) (v_6) edge (v_2) (v_6) edge (v_3) (v_6) edge (v_4) (v_6) edge (v_5); \end{tikzpicture} \caption{$W_5$, the wheel graph on six total vertices.} \label{fig:wheelgraph} \end{center} \end{figure} We now present the main combinatorial characterization. \begin{theorem} \label{thm:ourcombo} Let $G$ be a graph. Under Bayer's formulation of 3-colorability with coefficients in the field $\k=GF(2)$, $\nulla(G)=1$ if and only if $G$ is covered by length $2$ paths. \end{theorem} \begin{example} Let $n$ be an odd positive integer. In Example~\ref{ex:wheel}, we saw that the graph $W_n$ is covered by length two paths, so Theorem~\ref{thm:ourcombo} establishes that NulLA (applied to Bayer's formulation when $\k=GF(2)$) detects that this graph is non-3-colorable with a degree $1$ Nullstellensatz certificate. Odd wheels are known to be non-3-colorable for both computational and algebraic reasons, but the ability for NulLA to detect this with a degree $1$ certificate suggests that NulLA has the potential to be used not only as a computational tool but as a tool for automatic theorem proving. \end{example} \Fref{thm:ourcombo} also allows us to establish, combinatorially, that a graph does not have a degree 1 NulLA certificate (under Bayer's formulation when $\k=GF(2)$). \begin{figure}[ht] \begin{center} \begin{tikzpicture}[scale=1.3] \vertex[label=below:$v_6$](v_6) at (180:1.8) {}; \vertex[label=left:$v_2$](v_2) at (135:1.8) {}; \vertex[label=below:$v_4$](v_4) at (135:.8) {}; \vertex[label=above:$v_1$](v_1) at (90:1.8) {}; \vertex[label=right:$v_5$](v_5) at (45:1.8) {}; \vertex[label=below:$v_3$](v_3) at (45:.8) {}; \vertex[label=below:$v_7$](v_7) at (0:1.8) {}; \path (v_1) edge (v_2) (v_1) edge (v_4) (v_1) edge (v_3) (v_1) edge (v_5) (v_2) edge (v_4) (v_3) edge (v_5) (v_2) edge (v_6) (v_4) edge (v_6) (v_3) edge (v_7) (v_5) edge (v_7) (v_6) edge (v_7); \end{tikzpicture} \caption{Moser spindle.} \label{fig:moser} \end{center} \end{figure} \begin{proposition}\label{prop:moserspindle} Let $G$ be the Moser spindle (depicted in \Fref{fig:moser}). The graph $G$ does not have a degree $1$ NulLA certificate under Bayer's formulation when $\k=GF(2)$. \end{proposition} \begin{proof} Using \Fref{thm:ourcombo}, we will show that $\nulla(G)>1$ when $\k=GF(2)$. Suppose otherwise. By \Fref{thm:ourcombo}, $G$ is covered by length 2 paths, which we refer to collectively as $C$. We claim that the edge $v_6v_7$ can not be an edge in any length $2$ path in $C$. Indeed, assume without loss of generality that the path $v_6v_7v_k$ is in $C$ for some vertex $k \notin \{6,7\}$. Since the edge $v_6v_7$ is not on a $3$-cycle, $v_6v_k$ is not an edge. Moreover, since the edge $v_6v_7$ is not on a $4$-cycle, $v_6v_7v_k$ is the only member of $C$ whose endpoints are $v_6$ and $v_k$. But this is impossible because $v_6v_k$ is not an edge, so the number of paths in $C$ with $v_6$ and $v_k$ as endpoints must be even. Hence, there are no length $2$ paths in $C$ of the form $v_6v_7v_k$. Now since $v_6v_7v_k$ is not a member of $C$ for any $k$, $C$ certifies through \Fref{thm:ourcombo} that $\nulla(G\backslash v_6v_7)=1$. But this is a contradiction because $G\backslash v_6v_7$ is $3$-colorable. Thus, no set $C$ with the desired property exists, so $\nulla(G)\neq 1$. \end{proof} \Fref{prop:moserspindle} generalizes directly in the following way, providing a combinatorial obstruction to existence of a degree 1 Nullstellensatz certificate for Bayer's formulation when $\k=GF(2)$. \begin{corollary}\label{cor:corcomb} Let $\k=GF(2)$, and suppose $G$ is a non-3-colorable graph that contains an edge $e$ for which the following are true: \begin{itemize} \item $G\backslash e$ is 3-colorable, and \item $e$ is not an edge in a $3$-cycle nor a $4$-cycle of $G$. \end{itemize} Then $\nulla(G) > 1$. \end{corollary} \begin{remark}\label{ex:hard instances} One of the most celebrated constructions of very hard instances of graph 3-colorability is a construction of Mizuno and Nishihara \cite{Mizuno2008}. Corollary~\ref{cor:corcomb} is consistent with their findings. Indeed, in all the graphs they present in Figure 3 (see \cite{Mizuno2008}), the removal of any edge leaves a 3-colorable graph, and each of these graphs has an edge that does not lie on $3$ or $4$-cycle. This implies that when $\k=GF(2)$, $N_{\k}(G)>1$ for such graphs $G$, so computationally determining that they are not 3-colorable is not immediate under the NulLA paradigm. \end{remark} Alongside our combinatorial characterization, in Section 3 we begin the program of determining the Nullstellensatz degree of Bayer's formulation (with coefficients in $GF(2)$) for small non-3-colorable graphs. Most notably we prove \begin{theorem} \label{thm:lowdegree} If $\k=GF(2)$ and $|V(G)| \leq 12$, then $\nulla(G) \leq 4$. \end{theorem} %\noindent \textbf{Outline.} We begin in Section 2, introducing necessary preliminaries for the remainder of the article. In Section 3, we focus on developing a combinatorial characterization of non-3-colorable graphs that have degree 1 Nullstellensatz certificates. In particular, this section will give a proof of \Fref{thm:ourcombo}. Section 4 is dedicated to the proof of \Fref{thm:lowdegree} and investigating how the Nullstellensatz degree of non-3-colorable graphs change under certain graph operations. We conclude in Section 5 with avenues for future investigation. \section{Characterizing Degree $1$ Certificates} \label{sec:finitefields}% This section is dedicated to proving \Fref{thm:ourcombo}, and in particular developing a combinatorial characterization of non-3-colorable graphs $G$ for which $\nulla(G)=1$ (under Bayer's formulation with coefficients in $GF(2)$). We begin with a technical proposition that will be needed throughout: \begin{proposition} \label{prop:equiv} For a graph $G$ with vertex set $V=\{v_1,v_2,\dots,v_n\}$ and edge set $E$, the following are equivalent for Bayer's formulation when $\k=GF(2)$: \begin{enumerate} \item $\nulla(G)=1$. \item $1$ is a $\k$-linear combination of \begin{align} &x_i^3+1& \forall v_i\in V& \\ &x_k(x_i^2+x_ix_j+x_j^2)& \forall v_iv_j\in E, v_k\in V& \end{align} \item $1$ is a $\k$-linear combination of \begin{align} &x_i^2x_j+x_ix_j^2+1& \forall v_iv_j\in E& \\ &x_i^2x_k+x_ix_jx_k+x_j^2x_k& \forall v_iv_j\in E, v_k\in V, v_i\ne v_k\ne v_j& \end{align} \item $1$ is a $\k$-linear combination of \begin{align} &x_i^2x_j+x_ix_j^2+1& \forall v_iv_j\in E& \\ &x_i^2x_k+x_j^2x_k+x_ix_j^2+x_ix_k^2& \forall v_iv_j\in E, v_jv_k\in E& \end{align} \end{enumerate} \end{proposition} The above proposition finds alternate and equivalent sets of polynomials whose solution sets are the same as that of the system in Lemma 1.2. The last set of polynomials are particularly useful in uncovering our combinatorial characterization. The equivalence of the first three sets was proven in Theorem 2.1 of \cite{Omar2010}. The equivalence to the last set of polynomials follows an argument similar to the proof of Theorem 2.1 in \cite{Omar2010}. For completeness, we include a proof of this equivalence in the appendix. In proving \Fref{thm:ourcombo}, we will repeatedly appeal to the following immediate proposition: \begin{proposition} \label{prop:prop2} Let $G$ be a graph with vertex set $V=\{v_1,v_2,\dots, v_n\}$ and edge set $E$, and suppose $G$ is covered by a set $C$ of length $2$ paths. The following statements are equivalent: \begin{enumerate} \item The number of pairs $v_i,v_j\in V$ with $ii,k$ is odd. \end{enumerate} \end{proposition} We omit the proof of \Fref{prop:prop2} but illustrate an example. Consider the wheel graph $W_5$ as depicted in \Fref{fig:wheelgraph}, and the set $C=\{v_1v_6v_2,v_2v_6v_3,v_3v_6v_4,v_4v_6v_5,v_5v_6v_1\}$ of length $2$ paths that $G$ is covered by. All three conditions in \Fref{prop:prop2} are satisfied. For condition $1$, the pairs $\{v_1,v_2\}$, $\{v_2,v_3\}$, $\{v_3,v_4\}$, $\{v_4,v_5\}$, $\{v_1,v_5\}$ each have exactly 1 path in $C$ as their endpoints, and all other pairs have 0 paths as their endpoints, so the total number of pairs in question is 5. For condition $2$, the pairs $\{i,j\}$, with $ii,k$, so the total in question here is also $5$. %\begin{proof} % The first two statements are equivalent because a sum being odd is equivalent to the sum having an odd number of odd terms. Now, each path $(i,j,k)$ in $C$ %counts twice in this sum if $ii,k$ is odd, and % \item If $i,j \in V$ but $\{i,j\} \notin E$, then the number of paths in $C$ with $i$ and $j$ as endpoints is even. %\end{enumerate} %\end{theorem} \begin{proof}(of \Fref{thm:ourcombo}) Throughout this proof, for any set of polynomials $S$ in a polynomial ring whose coefficients are in $\k$, we denote by $\langle S \rangle_{\k}$ the linear span of $S$ over $\k$. Let $F$ be the following set of polynomials: \begin{align} &x_i^2x_j+x_ix_j^2+1& \forall v_iv_j \in E& \label{eq:firstset} \\ &x_i^2x_k+x_j^2x_k+x_ix_j^2+x_ix_k^2& \forall v_iv_j \in E, v_jv_k \in E& \label{eq:secondset} \end{align} By \Fref{prop:equiv}, we know that $\nulla(G)=1$ if and only if $1\in \langle F\rangle_{\k}$, so we must show that $1\in \langle F\rangle_{\k}$ if and only if $G$ is covered by a set $C$ of length $2$ paths. First suppose $G$ is covered by a set of length $2$ paths $C$. Consider the set $H\subset F$ consisting of the following polynomials: \begin{enumerate}\label{pathtypes} \item $x_i^2x_k+x_j^2x_k+x_ix_j^2+x_ix_k^2$ for each path $v_iv_jv_k \in C$, and \item $x_ix_j^2+x_jx_i^2+1$ for each $v_i,v_j\in V$ with $i2%%%%%%%%%%%%%%%%% %We now move on to showing that no non-3-colorable graphs have degree 1 Nullstellensatz certificates if the characteristic of $\k$ is $p$ for some prime $p>2$. From \Fref{prop:equiv}, an arbitrary graph $G$ has a degree $1$ certificate if and only if $1$ is in the linear span over $\k$ of the polynomials (5) and (6). We remark here that though \Fref{prop:equiv} requires char($\k$)=$2$, the proof of the previous statement holds over fields of arbitrary characteristic. %%\bayersthird % % So suppose we have a degree 1 certificate for $G$. Then there exist coefficients $q_{i,j}$ and $r_{i,j,k}$ in $\k$ such that %\begin{equation} % 1=\sum_{i,j}q_{i,j}(x_ix_j^2+x_jx_i^2+1)+\sum_{i,j,k}r_{i,j,k}(x_kx_i^2+x_ix_jx_k+x_kx_j^2). \label{eq:totalsum} %\end{equation} %Consider the summand %\begin{equation} % \sum_{i,j,k}r_{i,j,k}(x_kx_i^2+x_ix_jx_k+x_kx_j^2) \label{eq:partialsum} %\end{equation} %from the right-hand side of \fref{eq:totalsum}. Let $C_{i,j}$ denote the coefficient of $x_ix_j^2$ in \fref{eq:partialsum}, and let $S_{i,j,k}$ denote the coefficient of $x_ix_jx_k$ in \fref{eq:partialsum}. From \fref{eq:totalsum}, $S_{i,j,k}\equiv 0\pmod*p$. Now by comparing coefficients in \fref{eq:totalsum} and \fref{eq:partialsum} we have %\begin{equation} % \sum_{i,j}C_{i,j}=\sum_{i,j,k}2r_{i,j,k}=2\sum_{i,j,k}S_{i,j,k}\equiv 0\pmod*p \label{eq:cplus} %\end{equation} %Again by comparing coefficients, for the right-hand side of \fref{eq:totalsum} to sum to $1$, we must have the following two relations: %\begin{align} % \sum_{i,j}q_{i,j}&\equiv 1\pmod*p \\ % \sum_{i,j}2q_{i,j}+\sum_{i,j}C_{i,j}&\equiv 0\pmod*p, %\end{align} %the latter following because all terms of the form $x_ix_j^2$ must vanish. Combining these with \fref{eq:cplus}, we see that $0\equiv 2\pmod*p$. Therefore, there are no degree $1$ certificates if $p>2$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{NulLA on Small Graphs and Future Directions} Section 2 equipped us with a complete combinatorial understanding of the graphs $G$ for which $N_{\k}(G)=1$ when $\k=GF(2)$. By Theorem 2.1 of \cite{DeLoera2015}, $N_{\k}(G) \equiv 1 \ (\mbox{mod} \ 3)$, so in investigating Problem~\ref{prob:nulla}, the next natural step is determining when $N_{\k}(G)=4$. This section is devoted to a systematic study of this for small graphs. We first remark that, in order to find graphs with low minimum Nullstellensatz degree, we only need to focus on a subclass of non-3-colorable graphs. \begin{definition}[Definition 5.1.4 of \cite{West2001}] A non-3-colorable graph $G$ is \emph{4-critical} if for any edge $e\in E(G)$, $G\backslash e$ is 3-colorable. \end{definition} The following observation is fundamental for our purposes. See Chapter 5 of \cite{West2001} for a discussion of this. \begin{lemma}[\cite{West2001}] \label{lem:fourcrit} Every non-3-colorable graph has a 4-critical subgraph. \end{lemma} In light of the previous lemma, the following lemma tells us that 4-critical graphs provide upper bounds for the minimum Nullstellensatz degree of general non-3-colorable graphs. \begin{lemma}[Lemma 3.14 of \cite{DeLoeraLeeMarguliesOnn08}] \label{lem:subgraph} If $H$ and $G$ are non-3-colorable graphs with $H$ a subgraph of $G$, then $N_{\k}(H)\ge N_{\k}(G)$. \end{lemma} \Fref{lem:fourcrit} and \Fref{lem:subgraph} suggest that we solely focus on minimum degree Nullstellensatz certificates for 4-critical graphs. We computed minimum degree Nullstellensatz certificates for all such graphs on at most 12 vertices. A summary of the results is illustrated in \Fref{tab:smallnulla}. Some of the graphs represented in the data table are ones we have seen so far. For instance, the only 4-critical graph $G$ with $|V(G)|=4$ is the complete graph on four vertices, which is the wheel $W_3$. The graph on the fewest number of vertices whose minimum degree Nullstellensatz certificate is $4$ is the Moser spindle. One particular degree $4$ certificate, consistent with the vertex labeling in \Fref{fig:moser} is the following: \begin{dmath*} 1=(x_1x_2x_6+x_1x_2x_7+x_1x_4x_6+x_1x_4x_7+x_2x_6x_7+x_4x_6x_7)(x_1^3+1)+(x_1^2x_6+x_1^2x_7+x_1x_6x_7)(x_2^3+1)+(1)(x_3^3+1)+(x_4+x_7+x_1^2x_4x_6+x_1^2x_4x_7+x_1x_4x_6x_7)(x_1^2+x_1x_2+x_2^2)+(x_1)(x_1^2+x_1x_3+x_3^2)+(x_1+x_6+x_7+x_1^2x_2x_6+x_1^2x_2x_7+x_1x_2x_6x_7)(x_1^2+x_1x_4+x_4^2)+(x_3+x_7)(x_1^2+x_1x_5+x_5^2)+(x_1+x_2+x_6+x_1^2x_2x_6+x_1^2x_2x_7+x_1x_2x_6x_7)(x_2^2+x_2x_4+x_4^2)+(x_1+x_2+x_7)(x_2^2+x_2x_6+x_6^2)+(x_1+x_7)(x_3^2+x_3x_5+x_5^2)+(x_3)(x_3^2+x_3x_7+x_7^2)+(x_2+x_7)(x_4^2+x_4x_6+x_6^2)+(x_1+x_3)(x_5^2+x_5x_7+x_7^2)+(x_1)(x_6^2+x_6x_7+x_7^2) \end{dmath*} These observations now allow us to prove \Fref{thm:lowdegree}. \begin{table} \begin{center} \begin{tabular}{c|c|c|c} $|V|$ & $N_{\k}(G)=1$ & $N_{\k}(G)=4$ & Total $4$-critical graphs \\ \hline 4 & 1 & 0 & 1 \\ 5 & 0 & 0 & 0 \\ 6 & 1 & 0 & 1 \\ 7 & 1 & 1 & 2 \\ 8 & 2 & 3 & 5 \\ 9 & 5 & 16 & 21 \\ 10 & 13 & 137 & 150 \\ 11 & 38 & 1183 &1221 \\ 12 & 141 & 14440 &14581 \\ \hline Total & 202 & 15780 & 15982 \end{tabular} \caption{$N_{\k}(G)$ for $4$-critical graphs on at most $12$ vertices when $\k=GF(2)$.} \label{tab:smallnulla} \end{center} \end{table} \begin{proof}{(of \Fref{thm:lowdegree})} By \Fref{lem:fourcrit}, every non-3-colorable graph $G$ on at most 12 vertices has a 4-critical subgraph $H$. By \Fref{tab:smallnulla}, $N_{\k}(H)\in\{1,4\}$. \Fref{lem:subgraph} implies $N_{\k}(G)\leq N_{\k}(H)$. The result then follows by Theorem 2.1 of \cite{DeLoera2015}. \end{proof} Many pertinent questions arise from our study of the minimum Nullstellensatz degree of graphs under Bayer's formulation. First and foremost, unless P=NP, one should expect to find a family of graphs for which the minimum Nullstellensatz degree grows arbitrarily large (see Lemma 3.2 of \cite{DeLoeraLeeMarguliesOnn08} for a discussion of this). As evidenced by \Fref{tab:smallnulla}, an exhaustive search of the almost 16,000 4-critical graphs on at most 12 vertices indicates that a first step in this direction is to address the following problem: \begin{problem} \label{thm:highdeg} For any positive integer $t$, find a graph $G$ for which $N_{\k}(G)>t$. \end{problem} After exhaustive experimentation, the authors of \cite{DeLoeraLeeMarguliesOnn08} have yet to see an example resolving Problem~\ref{thm:highdeg} when $t=4$ for any finite field $\k$. One possible method for addressing Problem~\ref{thm:highdeg} is understanding what happens to the minimum Nullstellensatz degree under the famous Haj\'os construction. In his seminal paper \cite{Hajos1961}, Haj\'os defined a recursively constructed class of graphs, which he called $4$-constructible, in the following way: \begin{enumerate} \item[i)] $K_4$ is 4-constructible. \item[ii)] For any two non-adjacent vertices $u$ and $v$ in a 4-constructible graph $G$, the graph obtained from $G$ by adding an edge $e$ incident to $u$ and $v$ and contracting $e$ is also 4-constructible. \item[iii)] (Haj\'os Construction) For any two 4-constructible graphs $G$ and $H$, with $vw$ an edge of $G$, and $xy$ an edge of $H$, the graph obtained by identifying $v$ and $x$, removing $vw$ and $xy$, and adding the edge $wy$ is also 4-constructible. \end{enumerate} Haj\'os proved that the set of 4-constructible graphs is precisely the set of 4-critical graphs, so it is fundamental for us to determine what changes in the minimum Nullstellensatz degree of graphs when applying these constructions. Observe $N_{\k}(K_4)=1$, and by Lemma 3.14 of \cite{DeLoeraLeeMarguliesOnn08}, the minimum Nullstellensatz degree will not increase by applying construction ii). This leads us to the following fundamental question: \begin{problem} Let $G$ and $H$ be 4-critical graphs. What is the relationship between $N_{\k}(G)$, $N_{\k}(H)$ and the minimum Nullstellensatz degree of the graph obtained from $G$ and $H$ by applying the Haj\'os construction? \end{problem} \subsection*{Acknowledgments} The authors thank Jesus De Loera and Susan Margulies for fruitful discussions, the anonymous referees for their helpful feedback, and Eric Stucky for his assistance in typesetting. We also thank the referees for very helpful comments on edits to and the restructuring of the article. \appendix\section{Appendix} Here, we give a complete proof of Proposition~\ref{prop:equiv}. The equivalence of the first three sets of polynomials was proven in Theorem 2.1 of \cite{Omar2010}, so we proceed by establishing the equivalence of the fourth set of polynomials with the third. First, suppose we are given a polynomial $x_i^2x_k+x_j^2x_k+x_ix_j^2+x_ix_k^2$ in (8). Observe that \[x_i^2x_k+x_j^2x_k+x_ix_j^2+x_ix_k^2 = (x_i^2x_k+x_ix_jx_k+x_j^2x_k)+(x_j^2x_i+x_jx_kx_i+x_k^2x_i)\] since char($\k$)=2. The two summands on the right are polynomials in (6) because $v_iv_j$ and $v_jv_k$ lie in $E$, so any polynomial in (8) is a $\k$-linear combination of polynomials in (6), and hence the fourth condition implies the third. Now suppose the third condition holds, and we expressed $1$ as a $\k$-linear combination of the polynomials in (5) and (6) as follows: \begin{equation}\label{longeqn} 1 = \sum_{v_iv_j \in E} \alpha_{ij}(x_i^2x_j+x_ix_j^2+1) + \sum_{\substack{v_iv_j \in E \\ v_k \notin \{v_i,v_j\}, \ k \in V}} \beta_{ijk} (x_i^2x_k+x_ix_jx_k+x_j^2x_k). \end{equation} Fix vertices $v_i,v_j,v_k \in V$ with $v_iv_j \in E$. When the right-hand side of (\ref{longeqn}) is expanded, the coefficient of $x_ix_jx_k$ must be $0$. We now focus on the contribution of the polynomials in (5) and (6) to coefficient of $x_ix_jx_k$ on the right-hand side for a fixed set of vertices $\{v_i,v_j,v_k\}$. Without loss of generality, we can demand $v_iv_j \in E$. First, suppose neither $v_iv_k$ nor $v_jv_k$ are edges of $G$. Then the coefficient of $x_ix_jx_k$ is $\beta_{ijk}$. Comparing both sides of (\ref{longeqn}) implies $\beta_{ijk}=0$, and hence the polynomial $x_i^2x_k+x_ix_jx_k+x_j^2x_k$ does not appear at all on the right-hand side of (\ref{longeqn}). Now suppose all three of $v_iv_j,v_jv_k,v_iv_k$ are all in $E$. The polynomials in (5) and (6) that contain $x_ix_jx_k$ are \[ x_i^2x_k+x_ix_jx_k+x_j^2x_k, \ \ x_k^2x_i+x_ix_jx_k+x_j^2x_i, \ \ x_i^2x_j + x_ix_jx_k + x_k^2x_j, \] so if any of these appear as summands of the right-hand side of (\ref{longeqn}), then exactly two of them do (since char($\k$)=2). If none appear, we do not have to address this case, so assume exactly two appear, and without loss of generality assume they are the latter two. Then the combined contribution of these summands to the right-hand side of (\ref{longeqn}) is $(x_k^2x_i+x_ix_jx_k+x_j^2x_i )+ (x_i^2x_j + x_ix_jx_k + x_k^2x_j)$. But observe \[ (x_k^2x_i+x_ix_jx_k+x_j^2x_i )+ (x_i^2x_j + x_ix_jx_k + x_k^2x_j) = x_i^2x_j+x_k^2x_j + x_ix_j^2+x_ix_k^2 \] which is a polynomial in (8) since $v_iv_k,v_kv_j \in E$. Finally, suppose $v_iv_k \notin E, v_jv_k \in E$. This is the only remaining case since the case when $v_iv_k \in E, v_jv_k \notin E$ follows by symmetry. In this case, the only polynomials in (5) and (6) that contain $x_ix_jx_k$ as a summand are \[ x_i^2x_k+x_ix_jx_k+x_j^2x_k, \ \ x_j^2x_i+x_ix_jx_k+x_k^2x_i. \] Again, since the coefficient of $x_ix_jx_k$ must be $0$, either neither of these appear as summands in (\ref{longeqn}) or both do. Again, we only need consider the case when both appear. In this case, again since $\k=GF(2)$, $\beta_{ijk}=\beta_{kij}=1$. Observe then that the contribution of such polynomials to the right hand side of (\ref{longeqn}) is \[ (x_i^2x_k+x_ix_jx_k+x_j^2x_k )+ (x_j^2x_i+x_ix_jx_k+x_k^2x_i) = x_j^2x_i+x_k^2x_i+x_kx_i^2+x_kx_j^2, \] and the latter polynomial is a polynomial in (8) since $v_iv_j,v_jv_k \in E$. Thus if $1$ is a $\k$-linear combination of polynomials in (6) then it is a $\k$-linear combination of polynomials in (8). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bibliographystyle{plain} \begin{thebibliography}{99} \bibitem{Bayer82} D.A. Bayer. \newblock {\em The {D}ivision {A}lgorithm and the {H}ilbert {S}cheme}. \newblock PhD thesis, Harvard University, 1982. \bibitem{CoxLittleOShea92} D.~Cox, J.~Little, and D.~O'Shea. \newblock {\em Ideals, varieties, and algorithms}. \newblock Undergraduate Texts in Mathematics. Springer, 3 edition, 2007. \newblock An introduction to computational algebraic geometry and commutative algebra. \bibitem{Omar2010} J.~De~Loera, C.~Hillar, P.~Malkin, and M.~Omar. \newblock Recognizing graph theoretic properties through polynomial ideals. \newblock {\em Electronic Journal of Combinatorics}, 17:R114, 2010. \bibitem{DeLoeraLeeMalkinMargulies08} J.~De~Loera, J.~Lee, P.N. Malkin, and S.~Margulies. \newblock Hilbert's {N}ullstellensatz and an algorithm for proving combinatorial infeasibility. \newblock In {\em Proceedings of the Twenty-first International Symposium on Symbolic and Algebraic Computation (ISSAC 2008)}, 2008. \bibitem{DeLoeraLeeMarguliesOnn08} J.~De~Loera, J.~Lee, S.~Margulies, and S.~Onn. \newblock Expressing combinatorial problems by systems of polynomial equations and {H}ilbert's {N}ullstellensatz. \newblock {\em Combin. Probab. Comput.}, 18(4):551--582, 2009. \bibitem{DeLoera2015} J.~De~Loera, S.~Margulies, M.~Pernpeintner, E.~Rieldl, G.~Rolnick~D., Spencer, D.~Stasi, and Swenson J. \newblock Gr{\"o}bner bases and nullstellens{\"a}tze for graph-coloring ideals. \newblock In {\em Proceedings of the Twenty-seventh International Symposium on Symbolic and Algebraic Computation (ISSAC 2015)}, 2015. \bibitem{GouveiaParriloThomas2008} J.~Gouveia, P.~Parrilo, and R.R. Thomas. \newblock Theta bodies for polynomial ideals. \newblock {\em SIAM Journal on Optimization}, 20(4):2097--2118, 2010. \bibitem{Hajos1961} G.~Haj{\'o}s. \newblock {\"U}ber eine konstruktion nicht n-f{\"a}rbbarer graphen. \newblock {\em Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Nat. Reihe}, 10:116--117, 1961. \bibitem{Lasserre2000} J.~B. Lasserre. \newblock Global optimization with polynomials and the problem of moments. \newblock {\em SIAM J. Optim.}, 11(3):796--817 (electronic), 2000/01. \bibitem{Lovasz1994} L.~Lov{\'a}sz. \newblock Stable sets and polynomials. \newblock {\em Discrete Math.}, 124(1-3):137--153, 1994. \newblock Graphs and combinatorics (Qawra, 1990). \bibitem{LovaszSchrijver1991} L.~Lov{\'a}sz and A.~Schrijver. \newblock Cones of matrices and set-functions and $0$-$1$ optimization. \newblock {\em SIAM J. Optim.}, 1(2):166--190, 1991. \bibitem{Mizuno2008} K.~Mizuno and S.~Nishihara. \newblock Constructive generation of very hard 3-colorability instances. \newblock {\em Discrete Applied Mathematics}, 156(2):218--229, 2008. \bibitem{SheraliAdams1990} H.D. Sherali and W.P. Adams. \newblock A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. \newblock {\em SIAM J. Discrete Math.}, 3(3):411--430, 1990. \bibitem{West2001} D.B. West. \newblock {\em Introduction to Graph Theory}, volume~2. \newblock Prentice Hall Upper Saddle River, 2001. \end{thebibliography} \end{document}