- 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
 On cliques and Lagrangians of hypergraphs Bull. Korean Math. Soc. 2019 Vol. 56, No. 3, 569-583 https://doi.org/10.4134/BKMS.b180096Published online May 16, 2019Printed May 31, 2019 Qingsong Tang, Xiangde Zhang, Cheng Zhao Northeastern University; 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 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 Supported by : This research is partially supported by Chinese Universities Scientific Fund(No.N140504004) and the Doctoral Starting up Foundation of Liaoning Province(No.201601011). Downloads: Full-text PDF   Full-text HTML