Low degree Nullstellensatz certificates for 3-colorability

MaRDI QIDQ907253zbMATH OpenFDO

Authors N. E. Zubov

Publication date 25 January 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.04680, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p6

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

polynomial equations over a field \(\mathbb{k}\)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Symbolic computation and algebraic computation (68W30)

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 $mathbbk$. 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 $mathbbk=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 $mathbbk=GF(2)$.

Review text

Summary: In a seminal paper, \textit{J. De Loera} et. al [in: Proceedings of the 2008 international symposium on symbolic and algebraic computation, ISSAC 2008, Linz/Hagenberg, Austria, July 20--23, 2008. New York, NY: Association for Computing Machinery (ACM). 197--206 (2008; Zbl 1297.05229)] 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 \(\Bbbk\). 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 \(\Bbbk=\mathrm{GF}(2)\). This greatly simplifies the work of De Loera et. al [loc. cit.], 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 \(\Bbbk=\mathrm{GF}(2)\).

Recommendations

• Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
• Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
• Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
• Graph colouring is hard for algorithms based on Hilbert's Nullstellensatz and Gröbner bases
• A general approach to deriving the \(g\)-good-neighbor conditional diagnosability of interconnection networks

Cites work

• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Constructive generation of very hard 3-colorability instances
• Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
• Global optimization with polynomials and the problem of moments
• Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
• scientific article; zbMATH DE number 2200042 (Why is no real title available?)
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Recognizing graph theoretic properties with polynomial ideals
• Stable sets and polynomials
• Theta bodies for polynomial ideals

Cited in

(5)

• Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
• Transformation invariance in the combinatorial Nullstellensatz and nowhere-zero points of non-singular matrices
• Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
• Ramsey numbers through the lenses of polynomial ideals and Nullstellensätze
• An algebraic perspective on Ramsey numbers

This page was built for publication: Low degree Nullstellensatz certificates for 3-colorability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q907253)