- Current Issue - Ahead of Print Articles - All Issues - Search - Open Access - Information for Authors - Downloads - Guideline - Regulations ㆍPaper Submission ㆍPaper Reviewing ㆍPublication and Distribution - Code of Ethics - For Authors ㆍOnlilne Submission ㆍMy Manuscript - For Reviewers - For Editors
 Homogeneous multilinear functions on hypergraph cliques Bull. Korean Math. Soc. 2017 Vol. 54, No. 3, 1037-1067 https://doi.org/10.4134/BKMS.b160474Published online May 31, 2017 Xiaojun Lu, Qingsong Tang, Xiangde Zhang, and Cheng Zhao Northeastern University, Northeastern University, Northeastern University, Indiana State University Abstract : 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 Downloads: Full-text PDF