English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Systems of polynomial equations over the complex or real numbers can be usedto model combinatorial problems. In this way, a combinatorial problem isfeasible (e.g. a graph is 3-colorable, hamiltonian, etc.) if and only if arelated system of polynomial equations has a solution. In the first part ofthis paper, we construct new polynomial encodings for the problems of findingin a graph its longest cycle, the largest planar subgraph, the edge-chromaticnumber, or the largest k-colorable subgraph.  For an infeasible polynomial system, the (complex) Hilbert Nullstellensatzgives a certificate that the associated combinatorial problem is infeasible.Thus, unless P = NP, there must exist an infinite sequence of infeasibleinstances of each hard combinatorial problem for which the minimum degree of aHilbert Nullstellensatz certificate of the associated polynomial system grows.  We show that the minimum-degree of a Nullstellensatz certificate for thenon-existence of a stable set of size greater than the stability number of thegraph is the stability number of the graph. Moreover, such a certificatecontains at least one term per stable set of G. In contrast, for non-3-colorability, we found only graphs with Nullstellensatz certificates of degreefour.

Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and the Nullstellensatz