On graph-Lagrangians of hypergraphs containing dense subgraphs

DOI10.1007/S10957-013-0485-3zbMATH Open1317.90309arXiv1311.1409OpenAlexW2026696587MaRDI QIDQ467466FDOQ467466

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)

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}

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

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

zbMATH Keywords

maximum cliquehypergraphspolinomial optimization

Mathematics Subject Classification ID

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

Cites Work

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

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

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)