Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, Kilian Risse · 2025
Read Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz by Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, Kilian Risse (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-17022.txt.
Introduction
Some statements are hard to prove even on average, not just in crafted worst cases. Jonas Conneryd and co-authors prove such a result in a 2025 paper about graph coloring, the puzzle of coloring a network's points so neighbors differ. The question is whether three colors suffice for a given sparse random graph, phrased as an algebraic proof problem.
The authors show that the polynomial calculus proof system, and with it the Nullstellensatz system, needs linearly growing degree to refute three-colorability of these random graphs. A known bridge between degree and proof size turns that into strongly exponential lower bounds on the length of any such proof. The graphs tested are both regular random graphs and the classic Erdős-Rényi kind. The result is the full-length version of a conference paper on average-case hardness.
Catalog record
| CREATOR | Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, Kilian Risse |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 117 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-17022
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz Thanks: This is the full-length version of a paper with the same title that appeared in the Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’23) . Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, Kilian Risse Abstract We prove that polynomial calculus (and hence also Nullstellensatz) over any field requires linear degree to refute that sparse random regular graphs, as well as sparse Erdős-Rényi random graphs, are 3 3 -colourable. Using the known relation between size and degree for polynomial calculus proofs, this implies strongly exponential lower bounds on proof size. 1 Introduction Determining the chromatic number of a graph G , i.e., how many colours are needed for the vertices of G if no two vertices connected by an edge should have the same colour, is one of the classic 21 problems shown NP -complete in the seminal work of Karp [ Kar72 ] . This graph colouring problem , as it is also referred to, has been extensively studied since then, but there are still major gaps in our understanding. The currently best known approximation algorithm computes a graph colouring within at most a factor \mathrm{O}\bigl(n(\log\log n)^{2}/(\log n)^{3}\bigr) of the chromatic number [ Hal93 ] , and it is known that approximating this number to within a factor n^{1-\varepsilon} is NP -hard [ Zuc07 ] . Even under the promise that the graph is 3 -colourable , the most parsimonious algorithm with guaranteed polynomial running time needs \mathrm{O}\bigl(n^{0.19996}\bigr) colours [ KT17 ] . This is very far from the lower bounds that are known—it is NP -hard to (2k-1) -colour a k -colourable graph [ BBKO21 ] , but the question of whether colouring a 3 -colourable graph with 6 colours is NP -hard remains open [ KO22 ] . It is widely believed that any algorithm that colours graphs optimally has to run in exponential time in the worst case, and the currently fastest algorithm for 3 -colouring has time complexity \mathrm{O}\bigl(1.3289^{n}\bigr) [ BE05 ] . A survey on various algorithms and techniques for so-called exact algorithms for graph colouring can be found in [ Hus15 ] . Graph colouring instances of practical interest might not exhibit such exponential-time behaviour, however, and in such a context it is relevant to study algorithms without worst-case guarantees and examine how they perform in practice. To understand such algorithms from a computational complexity viewpoint, it is natural to investigate bounded models of computation that are strong enough to describe the reasoning performed by the algorithms and to prove unconditional lower bounds that hold in these models. 1.1 Previous Work Focusing on random graphs, McDiarmid [ McD84 ] developed a method for determining k -colourability that captures a range of algorithmic approaches. Beame et al. [ BCMM05 ] showed that this method could in turn be simulated by the resolution proof system [ Bla37 , DP60 , DLL62 , Rob65 ] , and established average-case exponential lower bounds for resolution proofs of non- k -colourability for random graph instances sampled so as not to be k -colourable with exceedingly high probability. Different algebraic approaches for k -colourability have been considered in [ AT92 , Lov94 , Mat74 , Mat04 ] . Bayer [ Bay82 ] seems to have been the first to use Hilbert’s Nullstellensatz to attack graph colouring. Informally, the idea is to write the problem as a set of polynomial equations \{p_{i}(x_{1},\ldots,x_{n})=0\mid i\in[m]\} in such a way that legal k -colourings correspond to common roots of these polynomials. Finding polynomials q_{1},\ldots,q_{m} such that \sum_{i=1}^{m}q_{i}p_{i}=1 then proves that the graph is not k -colourable. This latter equality is referred to as a Nullstellensatz certificate of non-colourability, and the degree of this certificate is the largest degree of any polynomial q_{i}p_{i} in the sum. Later papers based on Nullstellensatz and Gröbner bases, such as [ DL95 , Mnu01 , HW08 ] , culminated in an award-winning sequence of works [ DLMM08 , DLMO09 , DLMM11 , DMP+15 ] presenting algorithms with surprisingly good practical performance. For quite some time, no strong lower bounds were known for these algebraic methods or the corresponding proof systems Nullstellensatz [ BIK+94 ] and polynomial calculus [ CEI96 , ABRW02 ] . On the contrary, the authors of [ DLMO09 ] reported that essentially all benchmarks they studied turned out to have Nullstellensatz certificates of small constant degree. The degree lower bound k+1 for k colours in [ DMP+15 ] remained the best known until optimal, linear, degree lower bounds for polynomial calculus were established in [ LN17 ] using a reduction from so-called functional pigeonhole principle formulas [ MN15 ] . A more general reduction framework was devised in [ AO19 ] to obtain optimal degree lower bounds also for the proof systems Sherali-Adams [ SA90 ] and sums-of-squares [ Las01 , Par00 ] , as well as weakly exponential size lower bounds for Frege proofs [ CR79 , Rec75 ] of bounded depth. The lower bounds discussed in the previous paragraph are not quite satisfactory, in that it is not clear how much they actually tell us about the graph colouring problem, as opposed to the hardness of the problems being reduced from. In order to improve our understanding for a wider range of graph instances, it seems both natural and desirable to establish average-case lower bounds for random graphs, just as for resolution in [ BCMM05 ] . However, this goal has remained elusive for almost two decades, as pointed out, e.g., in [ MN15 , LN17 , Lau18 , BN21 ] . For sparse random graphs, where the number of edges is linear in the number of vertices, no superconstant degree lower bounds at all have been established for algebraic or semialgebraic proof systems. On the contrary, it was shown in [ BKM19 ] , improving on [ Coj05 ] , that degree- 2 sums-of-squares refutes k -colourability on random d -regular graphs asymptotically almost surely whenever {d\geq 4k^{2}} . For dense random graphs, the strongest lower bound seems to be the recent logarithmic degree bound in the sums-of-squares proof system for Erdős-Rényi random graphs with edge probability 1/2 and k=n^{1/2+\varepsilon} colours [ KM21 ] . Since this result is for a problem encoding using inequalities, however, it is not clear whether this has any implications for Nullstellensatz or polynomial calculus over the reals (which are known to be polynomially simulated by sums-of-squares). And for other fields nothing has been known for the latter two proof systems—not even logarithmic lower bounds. 1.2 Our Contribution In this work, we establish optimal, linear, degree lower bounds and exponential size lower bounds for polynomial calculus proofs of non-colourability of random graphs. Theorem 1.1 (informal). For any d\geq 6 , polynomial calculus (and hence also Nullstellensatz) requires asymptotically almost surely linear degree to refute that random d -regular graphs, as well as Erdős-Rényi random graphs, are 3 -colourable. These degree lower bounds hold over any field, and also imply exponential lower bounds on proof size. We prove our lower bound for the standard encoding in proof complexity, where binary variables x_{v,i} indicate whether vertex v is coloured