Bulletin of the
Korean Mathematical Society BKMS

Motzkin and Straus established a close connection between the maximum clique problem and a solution (namely graph-Lagrangian) to the maximum value of a class of homogeneous quadratic multilinear functions over the standard simplex of the Euclidean space in 1965. This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique problem in graphs. It is useful in practice if similar results hold for hypergraphs. In this paper, we develop a homogeneous multilinear function based on the structure of hypergraphs and their complement hypergraphs. Its maximum value generalizes the graph-Lagrangian. Specifically, we establish a connection between the clique number and the generalized graph-Lagrangian of $3$-uniform graphs, which supports the conjecture posed in this paper.

Keywords: cliques of hypergraphs, Colex ordering, graph-Lagrangians of hypergraphs, polynomial optimization

MSC numbers: Primary 05C35, 05C65, 05D99, 90C27