On cliques and Lagrangians of hypergraphs
Bull. Korean Math. Soc.
Published online 2019 May 16
Qingsong Tang, Xiangde Zhang, and Cheng Zhao
Northeastern University, Indiana State University
Abstract : Given a graph $G$, the Motzkin and Straus formulation of the maximum clique problem is the quadratic program (QP) formed from the adjacent matrix of the graph $G$ over the standard simplex. It is well-known that the global optimum value of this QP (called Lagrangian) corresponds to the clique number of a graph. It is useful in practice if similar results hold for hypergraphs. In this paper, we attempt to explore the relationship between the Lagrangian of a hypergraph and the order of its maximum cliques when the number of edges is in a certain range. Specifically, we obtain upper bounds for the Grpah-Lagrangian of a hypergraph when the number of edges is in a certain range. These results further support a conjecture introduced by Y. Peng and C. Zhao (2012) and extend a result of J. Talbot (2002). We also establish an upper bound of the clique number in terms of Lagrangians for hypergraphs.
Keywords : Cliques of hypergraphs, Colex ordering, Lagrangian of hypergraphs, Polynomial optimization
MSC numbers : 05C35,05C65,05D99,90C27
Full-Text :


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