Undecidability of linear inequalities in graph homomorphism densities
Undecidability of linear inequalities in graph homomorphism densities
复制标题
图同态密度中线性不等式的不可判定性
DOI：
10.1090/s0894-0347-2010-00687-x
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Sergey Norin
中科院分区：
文献类型：
--
作者：
Hamed Hatami;Sergey Norin
这篇文章的目的是表明，即使是最基本的问题，在渐近极值图论可以是高度非平凡的。研究了图的同态密度之间的线性不等式。在量子图的语言中，这样的不等式的有效性等价于相应的量子图的正性。类似于多项式的设置，可以表示为标记量子图的平方和的量子图必然是正的。Lov'asz问是否相反的情况也是正确的。我们回答这个问题，也是一个相关的问题，拉兹博罗夫在消极的引入明确有效的不平等，不满足所需的条件。我们解决这些问题的基础上减少从真实的多元多项式和使用的事实，即有正多项式，不能表示为多项式的平方和。
已知确定多元多项式是否为正的问题是可判定的。因此，很自然地会问：“确定同态密度之间的线性不等式的有效性的问题是可判定的吗？“我们对这个问题给出了否定的答案，这表明这种不平等在其完全普遍性方面本质上是困难的。此外，我们从这一事实推断，类似的阿廷的解决方案希尔伯特的第十七个问题不成立的设置量子图形。
The purpose of this article is to show that even the most elementary problems in asymptotic extremal graph theory can be highly non-trivial. We study linear inequalities between graph homomorphism densities. In the language of quantum graphs the validity of such an inequality is equivalent to the positivity of a corresponding quantum graph. Similar to the setting of polynomials, a quantum graph that can be represented as a sum of squares of labeled quantum graphs is necessarily positive. Lov\'asz asks whether the opposite is also true. We answer this question and also a related question of Razborov in the negative by introducing explicit valid inequalities that do not satisfy the required conditions. Our solution to these problems is based on a reduction from real multivariate polynomials and uses the fact that there are positive polynomials that cannot be expressed as sums of squares of polynomials.
It is known that the problem of determining whether a multivariate polynomial is positive is decidable. Hence it is very natural to ask "Is the problem of determining the validity of a linear inequality between homomorphism densities decidable?" We give a negative answer to this question which shows that such inequalities are inherently difficult in their full generality. Furthermore we deduce from this fact that the analogue of Artin's solution to Hilbert's seventeenth problem does not hold in the setting of quantum graphs.