Homogeneous multilinear functions on hypergraph cliques
Bull. Korean Math. Soc. 2017 Vol. 54, No. 3, 1037-1067
Published online April 10, 2017
Printed 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  

Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd