The connection between polynomial optimization, maximum cliques and Turan densities
The connection between polynomial optimization, maximum cliques and Turan densities
复制标题
多项式优化、最大派系和图兰密度之间的联系
DOI：
10.1016/j.dam.2017.03.014
复制
发表时间：
2017
影响因子：
1.1
通讯作者：
Peng Yuejian
中科院分区：
文献类型：
--
作者：
Wu Biao;Peng Yuejian
1965年，Motzkin-Straus建立了图的最大团和拉格朗日量之间的联系，拉格朗日量是由标准单纯形中的图确定的二次函数的最大值。这一联系给出了完全图的Turán密度的经典结果的一个证明。在20世纪80年代，Sidorenko和Frankl-Füredi进一步发展了超图Turán问题的方法。然而，拉格朗日量和图的最大团之间的联系不能扩展到超图。2009年，S. Rota Bulgaria和M. Pelillo定义了由r-一致超图确定的r次齐次多项式函数，并给出了该多项式函数的最小值与r-一致超图的最大团之间的关系。本文给出了非齐次多项式函数的局部（全局）极小与边含r-1和r个顶点的超图的极大（极大）团之间的联系。这种联系可以用来得到完全{r− 1，r}-型超图的Turán密度的上界。
Abstract In 1965, Motzkin–Straus established the connection between the maximum cliques and the Lagrangian of a graph, the maximum value of a quadratic function determined by a graph in the standard simplex. This connection gave a proof of the Turán’s classical result on Turán densities of complete graphs. In 1980’s, Sidorenko and Frankl–Füredi further developed this method for hypergraph Turán problems. However, the connection between the Lagrangian and the maximum cliques of a graph cannot be extended to hypergraphs. In 2009, S. Rota Bulò and M. Pelillo defined a homogeneous polynomial function of degree r determined by an r-uniform hypergraph and gave the connection between the minimum value of this polynomial function and the maximum cliques of an r-uniform hypergraph. In this paper, we provide a connection between the local (global) minimizers of non-homogeneous polynomial functions to the maximal (maximum) cliques of hypergraphs whose edges containing r− 1 and r vertices. This connection can be applied to obtain an upper bound on the Turán densities of complete {r− 1, r}-type hypergraphs.