Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz

DOI10.1017/S0963548309009894zbMath1197.05155arXiv0706.0578OpenAlexW2106138233MaRDI QIDQ3552513

Jesús A. De Loera, Jon Lee, Susan Margulies, Shmuel Onn

Publication date: 22 April 2010

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Extremal set theory (05D05) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (20)

Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization ⋮ Checking strict positivity of Kraus maps is NP-hard ⋮ An algebraic formulation of hypergraph colorings ⋮ Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits ⋮ Sum-of-squares certificates for Vizing's conjecture via determining Gröbner bases ⋮ On vanishing sums of roots of unity in polynomial calculus and sum-of-squares ⋮ Low degree Nullstellensatz certificates for 3-colorability ⋮ Ideals of graph homomorphisms ⋮ Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz ⋮ Handelman's hierarchy for the maximum stable set problem ⋮ Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz – Corrigendum ⋮ On the complexity of Hilbert refutations for partition ⋮ A Polyhedral Characterization of Border Bases ⋮ Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares ⋮ Privacy-preserving data splitting: a combinatorial approach ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Reformulations in Mathematical Programming: Definitions and Systematics ⋮ Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach ⋮ 2-colorability of \(r\)-uniform hypergraphs ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling

Cites Work

• Unnamed Item
• Unnamed Item
• Independence numbers of graphs and generators of ideals
• Nowhere-zero flow polynomials
• Semidefinite representations for finite varieties
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• Bounds for the degrees in the Nullstellensatz
• Symmetric polynomials and Hall's theorem
• Planar graphs and poset dimension
• Expressing combinatorial optimization problems by linear programs
• Colorings and orientations of graphs
• On uniquely 3-colorable graphs
• Stable sets and polynomials
• On the ideal theory of graphs
• The Hilbert zonotope and a polynomial time algorithm for universal Gröbner bases.
• Semidefinite programming relaxations for semialgebraic problems
• Triangle-free four-chromatic graphs
• Lower bounds for the polynomial calculus and the Gröbner basis algorithm
• Algebraic characterization of uniquely vertex colorable graphs
• Polynomials nonnegative on a grid and discrete optimization
• New upper bounds for kissing numbers from semidefinite programming
• Combinatorial Nullstellensatz
• Sharp Effective Nullstellensatz
• On Markov Chains for Independent Sets

This page was built for publication: Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz