The connection between polynomial optimization, maximum cliques and Turán densities

摘要

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 ?