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)

Full work available at URL https://doi.org/10.1137/23M1553273

zbMATH Keywords

graphs coloringgraphs with large girthHilbert's Nullstellensatz

Mathematics Subject Classification ID

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

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

• 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 colouring is hard for algorithms based on Hilbert's Nullstellensatz and Gröbner bases
• Graph Theory and Probability
• Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
• scientific article; zbMATH DE number 1256733 (Why is no real title available?)
• scientific article; zbMATH DE number 2174386 (Why is no real title available?)
• 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
• Über die vollen Invariantensysteme.
• Using Algebraic Geometry
• Weak orientability of matroids and polynomial equations

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)