On graph-Lagrangians of hypergraphs containing dense subgraphs
type: Item
instance of: scholarly article
title: On graph-Lagrangians of hypergraphs containing dense subgraphs
zbMATH Open document ID: 1317.90309
author: Cheng Zhao
author: Qingsong Tang
author: Yuejian Peng
author: Xiangde Zhang
published in: Journal of Optimization Theory and Applications
publication date: 2014-11-03T00:00:00Z
full work available at URL: https://arxiv.org/abs/1311.1409
review text: Lagrangians of \(r\)-uniform hypergraphs, or simply \( r\)-graphs, were introduced for 2-graphs by \textit{T. S. Motzkin} and \textit{E. G. Straus} [Can. J. Math. 17, 533--540 (1965; Zbl 0129.39902)]. They established a remarkable connection between the global maxima of the Lagrangian of a graph \(G\) over the standard simplex and the clique number of \(G\). Also, they gave a new proof of \textit{P. Turán}'s theorem [Mat. Fiz. Lapok 48, 436--452 (1941; Zbl 0026.26903)]. In order to explore the relationship between the Lagrangian of a hypergraph and the order of its maximum clique for hypergraphs when the number of edges is in certain ranges, two conjectures are proposed by \textit{Y. Peng} and \textit{C. Zhao} [Graphs Comb. 29, No. 3, 681--694 (2013; Zbl 1267.05185)]. In this paper, the authors provide upper bounds on the Lagrangian of a 3-graph containing dense subgraphs when the number of edges of 3-graphs is in certain ranges. The results presented in this paper provide substantial evidence for two conjectures which are proposed by Peng and Zhao [loc. cit.]. Also, the autors extend some results of Peng and Zhao [loc. cit.] and \textit{J. M. Talbot} [Comb. Probab. Comput. 11, No. 2, 199--216 (2002; Zbl 0998.05049)]. The authors of this paper specify that they are not able to extend the arguments in paper to verify conjectures of Peng and Zhao [loc. cit.] and a conjecture of \textit{P. Frankl} and \textit{Z. Füredi} [J. Comb. Theory, Ser. A 52, No. 1, 129--147 (1989; Zbl 0731.05030)] for more general case. When \( r \geq 4\), the computation is more complex.
reviewed by: Eleonor Ciurea
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6363600
zbMATH Keywords: hypergraphs
zbMATH Keywords: maximum clique
zbMATH Keywords: polinomial optimization
describes a project that uses: QUALEX
MaRDI profile type: Publication
OpenAlex ID: W2026696587
arXiv ID: 1311.1409
cites work: Q5781249
cites work: Maxima for Graphs and a New Proof of a Theorem of Turán
cites work: Evolution towards the maximum clique
cites work: Exact bounds on the order of the maximum clique of a graph.
cites work: A new trust region technique for the maximum weight clique problem
cites work: Continuous Characterizations of the Maximum Clique Problem
cites work: A global optimization approach for solving the maximum clique problem
cites work: A Continuous-Based Approach for Partial Clique Enumeration
cites work: Extremal problems whose solutions are the blowups of the small Witt- designs
cites work: Hypergraphs do not jump
cites work: Extremals of functions on graphs with applications to graphs and hypergraphs
cites work: A generalization of the Motzkin-Straus theorem to hypergraphs
cites work: A Motzkin-Straus type result for 3-uniform hypergraphs
cites work: Lagrangians of Hypergraphs
cites work: A hypergraph extension of Turán's theorem
cites work: On Lagrangians of \(r\)-uniform hypergraphs
DOI: 10.1007/S10957-013-0485-3
description: scientific article; zbMATH DE number 6363600