HOMOGENEOUS MULTILINEAR FUNCTIONS ON HYPERGRAPH CLIQUES

作者：Lu, Xiaojun^*; Tang, Qingsong; Zhang, Xiangde; Zhao, Cheng

来源：Bulletin of the Korean Mathematical Society, 2017, 54(3): 1037-1067.

DOI：10.4134/BKMS.b160474

• cliques of hypergraphs
• Colex ordering
• graph-Lagrangians of hypergraphs
• polynomial optimization

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.

• 出版日期2017
• 单位东北大学