Graphs with large girth and chromatic number are hard for Nullstellensatz

DOI10.1137/23M1553273MaRDI QIDQ6573006zbMATH OpenFDO

Authors Julian Romero, Levent Tunçel

Publication date 16 July 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

graphs with large girthHilbert's Nullstellensatzgraphs coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Combinatorial aspects of algebraic geometry (05E14)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1256733 (Why is no real title available?)
• scientific article; zbMATH DE number 2174386 (Why is no real title available?)
• A comprehensive analysis of polyhedral lift-and-project methods
• A generalized method for proving polynomial calculus degree lower bounds
• Algèbre linéaire sur $K[X_1,\dots,X_n]$ et élimination
• Another Simple Proof of the High Girth, High Chromatic Number Theorem
• Coloring, sparseness and girth
• Combinatorial Nullstellensatz
• Constructive generation of very hard 3-colorability instances
• Convex relaxations and integrality gaps
• Good degree bounds on Nullstellensatz refutations of the induction principle
• Graph Theory and Probability
• Graph colouring is hard for algorithms based on Hilbert's Nullstellensatz and Gröbner bases
• Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Lower bounds for the polynomial calculus
• On chromatic number of finite set-systems
• Proof Complexity Meets Algebra
• Ramanujan graphs
• Recognizing graph theoretic properties with polynomial ideals
• Sharp Effective Nullstellensatz
• The relative complexity of NP search problems
• Using Algebraic Geometry
• Weak orientability of matroids and polynomial equations
• Über die vollen Invariantensysteme.

This page was built for publication: Graphs with large girth and chromatic number are hard for Nullstellensatz

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