Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949680 | Discrete Applied Mathematics | 2017 | 8 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Biao Wu, Yuejian Peng,