Tropicalization of graph profiles
Tropicalization of graph profiles
复制标题
图形配置文件的热带化
DOI：
10.1090/tran/8643
复制
发表时间：
2022
影响因子：
1.3
通讯作者：
Thomas, Rekha
中科院分区：
文献类型：
--
作者：
Blekherman, Grigoriy;Raymond, Annie;Singh, Mohit;Thomas, Rekha
图轮廓记录了固定有限图集的所有可能密度。配置文件可能非常复杂；例如，任何三元组连通图的完整配置文件都是未知的，而关于超图配置文件则知之甚少。我们介绍了图和超图轮廓的热带化。在代数几何中，热带化是一个研究得很好的运算，它用它的“组合阴影”代替了各种各样(有限个代数方程的实解或复解的集合)。我们证明了图轮廓的热带化是一个闭凸锥，它仍然捕捉到有趣的组合信息。我们显式地计算了完全超图和星形超图的任意集合的这些热带化。我们证明了它们是有理多面体锥体，尽管在某些情况下相应的轮廓甚至不是半代数的。然后，我们使用热带化法证明了对平方和方法的强大限制，等价于Cauchy-Schwarz演算，以检验(弱于证明)图密度不等式的有效性。特别地，我们证明了平方和不能检验简单的二叉图密度不等式，甚至不能检验它们的近似。给出了这类不等式的小的具体例子，其中包括著名的奇长度路的Blakley-Roy不等式。因此，这些简单的不等式不能写成图形密度平方的有理和。参考文献
A graph profile records all possible densities of a fixed finite set of graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected graphs is not known, and little is known about hypergraph profiles. We introduce the tropicalization of graph and hypergraph profiles. Tropicalization is a well-studied operation in algebraic geometry, which replaces a variety (the set of real or complex solutions to a finite set of algebraic equations) with its “combinatorial shadow”. We prove that the tropicalization of a graph profile is a closed convex cone, which still captures interesting combinatorial information. We explicitly compute these tropicalizations for arbitrary sets of complete and star hypergraphs. We show they are rational polyhedral cones even though the corresponding profiles are not even known to be semialgebraic in some of these cases. We then use tropicalization to prove strong restrictions on the power of the sums of squares method, equivalently Cauchy-Schwarz calculus, to test (which is weaker than certification) the validity of graph density inequalities. In particular, we show that sums of squares cannot test simple binomial graph density inequalities, or even their approximations. Small concrete examples of such inequalities are presented, and include the famous Blakley-Roy inequalities for paths of odd length. As a consequence, these simple inequalities cannot be written as a rational sum of squares of graph densities. References