On graph-Lagrangians of hypergraphs containing dense subgraphs

DOI10.1007/S10957-013-0485-3MaRDI QIDQ467466zbMATH OpenOpenAlexFDO

Authors Cheng Zhao, Qingsong Tang, Yuejian Peng, Xiangde Zhang

Publication date 3 November 2014

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.1409

zbMATH Keywords

maximum cliquehypergraphspolinomial optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Abstract: Motzkin and Straus established a remarkable connection between the maximum clique and the Lagrangian of a graph in 1965. This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique number in graphs. It is useful in practice if similar results hold for hypergraphs. In this paper, we provide upper bounds on the Lagrangian of a hypergraph containing dense subgraphs when the number of edges of the hypergraph is in certain ranges. These results support a pair of conjectures introduced by Y. Peng and C. Zhao (2012) and extend a result of J. Talbot (2002). keywords{Cliques of hypergraphs and Colex ordering and Lagrangians of hypergraphs and Polynomial optimization}

Recommendations

• On Lagrangians of \(r\)-uniform hypergraphs
• Model-order reduction ofkth order MIMO dynamical systems using blockkth order Krylov subspaces
• On cliques and Lagrangians of hypergraphs
• Maximum cliques of hypergraphs and polynomial optimization
• Homogeneous multilinear functions on hypergraph cliques

Cites work

• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A Continuous-Based Approach for Partial Clique Enumeration
• A Motzkin-Straus type result for 3-uniform hypergraphs
• A generalization of the Motzkin-Straus theorem to hypergraphs
• A global optimization approach for solving the maximum clique problem
• A hypergraph extension of Turán's theorem
• A new trust region technique for the maximum weight clique problem
• Continuous Characterizations of the Maximum Clique Problem
• Evolution towards the maximum clique
• Exact bounds on the order of the maximum clique of a graph.
• Extremal problems whose solutions are the blowups of the small Witt- designs
• Extremals of functions on graphs with applications to graphs and hypergraphs
• Hypergraphs do not jump
• Lagrangians of Hypergraphs
• Maxima for Graphs and a New Proof of a Theorem of Turán
• On Lagrangians of \(r\)-uniform hypergraphs

Cited in

(11)

• Some Motzkin-Straus type results for non-uniform hypergraphs
• Connection between the clique number and the Lagrangian of 3-uniform hypergraphs
• Dense 3-uniform hypergraphs containing a large clique
• On Lagrangians of \(r\)-uniform hypergraphs
• Model-order reduction ofkth order MIMO dynamical systems using blockkth order Krylov subspaces
• On Frankl and Füredi's conjecture for 3-uniform hypergraphs
• On graph-Lagrangians and clique numbers of 3-uniform hypergraphs
• On the largest graph-Lagrangian of 3-graphs with fixed number of edges
• On cliques and Lagrangians of hypergraphs
• Maximisers of the hypergraph Lagrangian outside the principal range
• Lagrangians of Hypergraphs

Describes a project that uses

Uses Software

• QUALEX

This page was built for publication: On graph-Lagrangians of hypergraphs containing dense subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q467466)