发帖
雷达卡
摘要翻译：
复数或实数上的多项式方程组可用于组合问题的建模。这样，一个组合问题是可行的（例如图是3-可色的，哈密顿的，等等）当且仅当一个相关的多项式方程组有解。在本文的第一部分，我们构造了一个新的多项式编码，用于求一个图的最长圈、最大平面子图、边色数或最大k-可色子图的问题。对于一个不可行的多项式系统，复Hilbert Nullstellensatz证明了相关的组合问题是不可行的。因此，除非P=NP，否则每个硬组合问题必然存在无穷多个不可行实例序列，对于这些不可行实例序列，相关多项式系统的Hilbert Nullstellensatz证明的最小次数增长。我们证明了不存在大于图的稳定数的稳定集的Nullstellensatz证明的最小度是图的稳定数。另外，这样的证明在G的每个稳定集上至少包含一个项。相反，对于非3-可色性，我们只发现具有4度Nullstellensatz证明的图。
---
英文标题：
《Expressing Combinatorial Optimization Problems by Systems of Polynomial
Equations and the Nullstellensatz》
---
作者：
J.A. De Loera, J. Lee, S. Margulies, S. Onn
---
最新提交年份：
2007
---
分类信息：
一级分类：Mathematics 数学
二级分类：Combinatorics 组合学
分类描述：Discrete mathematics, graph theory, enumeration, combinatorial optimization, Ramsey theory, combinatorial game theory
离散数学，图论，计数，组合优化，拉姆齐理论，组合对策论
--
一级分类：Mathematics 数学
二级分类：Algebraic Geometry 代数几何
分类描述：Algebraic varieties, stacks, sheaves, schemes, moduli spaces, complex geometry, quantum cohomology
代数簇，叠，束，格式，模空间，复几何，量子上同调
--
---
英文摘要：
Systems of polynomial equations over the complex or real numbers can be used to model combinatorial problems. In this way, a combinatorial problem is feasible (e.g. a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution. In the first part of this paper, we construct new polynomial encodings for the problems of finding in a graph its longest cycle, the largest planar subgraph, the edge-chromatic number, or the largest k-colorable subgraph. For an infeasible polynomial system, the (complex) Hilbert Nullstellensatz gives a certificate that the associated combinatorial problem is infeasible. Thus, unless P = NP, there must exist an infinite sequence of infeasible instances of each hard combinatorial problem for which the minimum degree of a Hilbert Nullstellensatz certificate of the associated polynomial system grows. We show that the minimum-degree of a Nullstellensatz certificate for the non-existence of a stable set of size greater than the stability number of the graph is the stability number of the graph. Moreover, such a certificate contains at least one term per stable set of G. In contrast, for non-3- colorability, we found only graphs with Nullstellensatz certificates of degree four.
---
PDF链接：
https://arxiv.org/pdf/0706.0578
京公网安备 11010802022788号
