Metraipolis › archive › dc_fa9365d7baa2
Nullstellensatz degree under Hajós joins and vertex identifications — arXiv:2609.14865
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.14865
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T01:25:24.089Z
- SHA-256 of the archived text
1d99869a93204d4276208af264dd0b489855b99351235bb9056d379e8c5df9a1- Stable URL of this page
https://metraipolis.com/documento/dc_fa9365d7baa2
How to cite
Nullstellensatz degree under Hajós joins and vertex identifications — arXiv:2609.14865 — arXiv (en), https://arxiv.org/abs/2609.14865 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fa9365d7baa2 (Metraipolis archive dc_fa9365d7baa2, sha256 1d99869a93204d4276208af264dd0b489855b99351235bb9056d379e8c5df9a1)
BibTeX
@misc{dcfa9365d7baa2,
title = {Nullstellensatz degree under Hajós joins and vertex identifications — arXiv:2609.14865},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.14865},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fa9365d7baa2; sha256 1d99869a93204d4276208af264dd0b489855b99351235bb9056d379e8c5df9a1},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.14865. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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)\leq m+k$. When deletion of the selected edge makes each input $k$-colorable, we also have $N_{k,\F}(J)\geq m$; the degree congruence then gives $N_{k,\F}(J)\in\{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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.14865 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T00:39:30.227Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).