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

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.