Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility

zbMath1297.05229arXiv0801.3788MaRDI QIDQ5301623

Jesús A. De Loera, Peter N. Malkin, Jon Lee, Susan Margulies

Publication date: 20 January 2009

Full work available at URL: https://arxiv.org/abs/0801.3788

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Solving polynomial systems; resultants (13P15)

Related Items (10)

Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization ⋮ Gröbner bases techniques for an \(S\)-packing \(k\)-coloring of a graph ⋮ Chordal Networks of Polynomial Ideals ⋮ Sum-of-squares certificates for Vizing's conjecture via determining Gröbner bases ⋮ Alternatives for testing total dual integrality ⋮ Low degree Nullstellensatz certificates for 3-colorability ⋮ Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz ⋮ DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization ⋮ A Polyhedral Characterization of Border Bases ⋮ Approximating amoebas and coamoebas by sums of squares

This page was built for publication: Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility