Simple Graph Density Inequalities with No Sum of Squares Proofs
Simple Graph Density Inequalities with No Sum of Squares Proofs
复制标题
没有平方和证明的简单图密度不等式
DOI：
10.1007/s00493-019-4124-y
复制
发表时间：
2020
期刊：
影响因子：
1.1
通讯作者：
Thomas, Rekha R.
中科院分区：
文献类型：
--
作者：
Blekherman, Grigoriy;Raymond, Annie;Singh, Mohit;Thomas, Rekha R.
建立图密度之间的不等式是极值组合学的核心追求。证明图密度表达式的非负性的标准工具是将其写成平方和。在本文中，我们确定了一个简单的条件下，图密度表达式不能是平方和。利用这个结果，我们证明了当路径长度为奇数时，Blakley-Roy不等式没有平方和证明.我们还表明，同样的布莱克利-罗伊不等式不能被证明的平方和使用乘数的形式加一个平方和。这些结果回答了Lovász提出的两个问题。我们的主要工具是再次使用，以表明最小的开放情况下，西多连科的固定不等式不能被证明的平方和。最后，我们证明了我们的设置与Razborov和Lovász-Szegedy的现有框架等效，因此我们的结果也适用于这些设置。
Establishing inequalities among graph densities is a central pursuit in extremal combinatorics. A standard tool to certify the nonnegativity of a graph density expression is to write it as a sum of squares. In this paper, we identify a simple condition under which a graph density expression cannot be a sum of squares. Using this result, we prove that the Blakley-Roy inequality does not have a sum of squares certificate when the path length is odd. We also show that the same Blakley-Roy inequalities cannot be certified by sums of squares using a multiplier of the form one plus a sum of squares. These results answer two questions raised by Lovász. Our main tool is used again to show that the smallest open case of Sidorenko's conjectured inequality cannot be certified by a sum of squares. Finally, we show that our setup is equivalent to existing frameworks by Razborov and Lovász-Szegedy, and thus our results hold in these settings too.
登录
查看更多内容
算术投影的界限以及 KAKEYA 猜想的应用
影响因子：
1
作者：
N. Katz;T. Tao
通讯作者：
T. Tao
西多伦科猜想的两种方法
DOI：
10.1090/tran/6487
发表时间：
2013
期刊：
arXiv: Combinatorics
影响因子：
--
作者：
J. Kim;Choongbum Lee;Joonkyung Lee
通讯作者：
Joonkyung Lee
图同态密度中线性不等式的不可判定性
DOI：
10.1090/s0894-0347-2010-00687-x
发表时间：
2010
期刊：
arXiv: Combinatorics
影响因子：
--
作者：
Hamed Hatami;Sergey Norin
通讯作者：
Sergey Norin
影响因子：
1.1
作者：
Conlon, David;Lee, Joonkyung
通讯作者：
Lee, Joonkyung
DOI：
10.5802/alco.5
发表时间：
2015-07
期刊：
ArXiv
影响因子：
--
作者：
Annie Raymond;Mohit Singh;Rekha R. Thomas
通讯作者：
Annie Raymond;Mohit Singh;Rekha R. Thomas