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).