Connection Between Polynomial Optimization and Maximum Cliques of Non-Uniform Hypergraphs

摘要

In Motzkin and Straus (Canad. J. Math 498 17, 533540 1965) provided a connection between the order of a maximum clique in a graph G and the Lagrangian function of G. In Rota Bul and Pelillo (Optim. Lett. 500 3, 287295 2009) extended the Motzkin-Straus result to r-uniform hypergraphs by establishing a one-to-one correspondence between local (global) minimizers of a family of homogeneous polynomial functions of degree r and the maximal (maximum) cliques of an r-uniform hypergraph. In this paper, we study similar optimization problems and obtain the connection to maximum cliques for {s, r}-hypergraphs and {p, s, r}-hypergraphs, which can be applied to obtain upper bounds on the Turan densities of the complete {s, r}-hypergraphs and {p, s, r}-hypergraphs.