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

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