Nullstellensatz degree under Hajós joins and vertex identifications
Abstract
We study the minimum coefficient degree Nk,F(G) of a Nullstellensatz certificate for Bayer's k-coloring equations, where the characteristic of F does not divide k. If J is a \HJ\ join of non-k-colorable graphs G,H and m=max{Nk,F(G),Nk,F(H)}, then Nk,F(J)≤ m+k. When deletion of the selected edge makes each input k-colorable, we also have Nk,F(J)≥ m; the degree congruence then gives Nk,F(J)∈{m,m+k}. This partially answers a question of Li, Lowenstein, and Omar. For three-coloring over F2, we construct an infinite $4$-critical family of exact degree seven, attaining the bound at input degree four. In contrast, every graph constructed from K4 solely by \HJ\ joins has degree O(log n) and a certificate with polynomially many terms: joins preserve treewidth at most three, and balanced separators yield low-degree certificates. Additional vertex identifications are excluded from this obstruction. We classify all single identifications of the $25$-vertex base graph; exactly $36$ preserve degree seven, producing $24$-vertex $4$-critical graphs of treewidth four. A compressed self-join at adjacent true twins prevents degree loss and gives a repeatable rule adding four vertices per round. The rule does not establish degree amplification or preservation of criticality. Exact witnesses and standalone verification programs accompany the finite results.
Related
- The DP color function of joins and vertex-gluing of hypergraphs
- Degree profiles of uniform polynomial consequences: Linear lower bounds for Nullstellensatz and Polynomial Calculus
- A Unified Linear Programming Approach for Maximizing Vertex-Degree-Based Indices of Trees
- Perfect Codes in Cayley Graphs of Hajós Groups
- Rank identifications in join-meet ideals of thin distributive lattices
BibTeX
@misc{xie2026nullstellensatz,
title = {{Nullstellensatz degree under Hajós joins and vertex identifications}},
author = {Ying Xie},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.14865},
eprint = {2609.14865},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14865},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Nullstellensatz degree under Hajós joins and vertex identifications
AU - Ying Xie
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.14865
UR - https://arxiv.org/abs/2609.14865
AB - We study the minimum coefficient degree N_k,F(G) of a Nullstellensatz certificate for Bayer's k-coloring equations, where the characteristic of F does not divide k. If J is a \HJ\ join of non-k-colorable graphs G,H and m=max{N_k,F(G),N_k,F(H)}, then N_k,F(J)≤ m+k. When deletion of the selected edge makes each input k-colorable, we also have N_k,F(J)≥ m; the degree congruence then gives N_k,F(J)∈{m,m+k}. This partially answers a question of Li, Lowenstein, and Omar. For three-coloring over F_2, we construct an infinite $4$-critical family of exact degree seven, attaining the bound at input degree four. In contrast, every graph constructed from K_4 solely by \HJ\ joins has degree O(log n) and a certificate with polynomially many terms: joins preserve treewidth at most three, and balanced separators yield low-degree certificates. Additional vertex identifications are excluded from this obstruction. We classify all single identifications of the $25$-vertex base graph; exactly $36$ preserve degree seven, producing $24$-vertex $4$-critical graphs of treewidth four. A compressed self-join at adjacent true twins prevents degree loss and gives a repeatable rule adding four vertices per round. The rule does not establish degree amplification or preservation of criticality. Exact witnesses and standalone verification programs accompany the finite results.
ER -