论文标题
加权图同态密度的多项式不平等的不可证明性
Undecidability of polynomial inequalities in weighted graph homomorphism densities
论文作者
论文摘要
极端组合主义者中的许多问题和猜想涉及图形密度之间的多项式不等式，我们允许边缘具有实际权重。使用图形限制理论，我们可以等效地评估内核$ W $的同态密度中的多项式表达式，即来自$ [0,1]^2 \ to \ Mathbb {r} $的对称，有限和可测量的函数$ W $。 In 2011, Hatami and Norin proved a fundamental result that it is undecidable to determine the validity of polynomial inequalities in homomorphism densities for graphons (i.e., the case where the range of $W$ is $[0,1]$, which corresponds to unweighted graphs, or equivalently, to graphs with edge weights between $0$ and $1$).对于所有内核或具有范围$ [-1,1] $的内核的相应问题，例如，对于所有内核或内核。对于任何$ a> 0 $，对于任何包含所有内核的范围$ \ {0，a \} $的内核的多项式不等式的不可证明性。该结果还回答了洛瓦斯（Lovász）提出的一个问题，该问题涉及核中核中同态密度不平等有效性的计算有效证书。
Many problems and conjectures in extremal combinatorics concern polynomial inequalities between homomorphism densities of graphs where we allow edges to have real weights. Using the theory of graph limits, we can equivalently evaluate polynomial expressions in homomorphism densities on kernels $W$, i.e., symmetric, bounded, and measurable functions $W$ from $[0,1]^2 \to \mathbb{R}$. In 2011, Hatami and Norin proved a fundamental result that it is undecidable to determine the validity of polynomial inequalities in homomorphism densities for graphons (i.e., the case where the range of $W$ is $[0,1]$, which corresponds to unweighted graphs, or equivalently, to graphs with edge weights between $0$ and $1$). The corresponding problem for more general sets of kernels, e.g., for all kernels or for kernels with range $[-1,1]$, remains open. For any $a > 0$, we show undecidability of polynomial inequalities for any set of kernels which contains all kernels with range $\{0,a\}$. This result also answers a question raised by Lovász about finding computationally effective certificates for the validity of homomorphism density inequalities in kernels.
