Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
From MaRDI portal
Abstract: Systems of polynomial equations over an algebraically-closed field K can be used to concisely model many combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over K. In this paper, we investigate an algorithm aimed at proving combinatorial infeasibility based on the observed low degree of Hilbert's Nullstellensatz certificates for polynomial systems arising in combinatorics and on large-scale linear-algebra computations over K. We report on experiments based on the problem of proving the non-3-colorability of graphs. We successfully solved graph problem instances having thousands of nodes and tens of thousands of edges.
Recommendations
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
- Combinatorial Nullstellensatz
- Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
- A general approach to deriving the \(g\)-good-neighbor conditional diagnosability of interconnection networks
- Graph colouring is hard for algorithms based on Hilbert's Nullstellensatz and Gröbner bases
Cited in
(20)- Combinatorial versus decision-theoretic components of impossibility theorems
- Recognizing graph theoretic properties with polynomial ideals
- Gröbner bases techniques for an \(S\)-packing \(k\)-coloring of a graph
- Alternatives for testing total dual integrality
- Computation with polynomial equations and inequalities arising in combinatorial optimization
- Computing small certificates of inconsistency of quadratic fewnomial systems
- Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
- Towards Hilbert's 24th Problem: Combinatorial Proof Invariants
- Graph colouring is hard for algorithms based on Hilbert's Nullstellensatz and Gröbner bases
- Chordal networks of polynomial ideals
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- Approximating amoebas and coamoebas by sums of squares
- A Polyhedral Characterization of Border Bases
- Sum-of-squares certificates for Vizing's conjecture via determining Gröbner bases
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
- Graphs with large girth and chromatic number are hard for Nullstellensatz
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Ramsey numbers through the lenses of polynomial ideals and Nullstellensätze
- An algebraic perspective on Ramsey numbers
- Low degree Nullstellensatz certificates for 3-colorability
This page was built for publication: Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5301623)
