On Lagrangians of r-uniform hypergraphs
From MaRDI portal
Publication:498456
DOI10.1007/S10878-013-9671-3zbMATH Open1332.90330arXiv1212.2795OpenAlexW2068939338MaRDI QIDQ498456FDOQ498456
Authors: Cheng Zhao, Yuejian Peng, Qingsong Tang 
Publication date: 28 September 2015
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Abstract: A remarkable connection between the order of a maximum clique and the Lagrangian of a graph was established by Motzkin and Straus in [7]. This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique number in graphs. It has been also applied in spectral graph theory. Estimating the Lagrangians of hypergraphs has been successfully applied in the course of studying the Turan densities of several hypergraphs as well. It is useful in practice if Motzkin-Straus type results hold for hypergraphs. However, the obvious generalization of Motzkin and Straus' result to hypergraphs is false. We attempt to explore the relationship between the Lagrangian of a hypergraph and the order of its maximum cliques for hypergraphs when the number of edges is in certain range. In this paper, we give some Motzkin-Straus type results for r-uniform hypergraphs. These results generalize and refine a result of Talbot in [19] and a result in [11].
Full work available at URL: https://arxiv.org/abs/1212.2795
Recommendations
- Model-order reduction ofkth order MIMO dynamical systems using blockkth order Krylov subspaces
- On graph-Lagrangians of hypergraphs containing dense subgraphs
- Some Motzkin-Straus type results for non-uniform hypergraphs
- Maximum cliques of hypergraphs and polynomial optimization
- A Motzkin-Straus type result for 3-uniform hypergraphs
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
- Some results on Lagrangians of hypergraphs
- On finding Lagrangians of 3-uniform hypergraphs.
- Lagrangians of 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
- 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
- Spectral bounds for the clique and independence numbers of graphs
- Exact bounds on the order of the maximum clique of a graph.
- A global optimization approach for solving the maximum clique problem
Cited In (22)
- Some Motzkin-Straus type results for non-uniform hypergraphs
- An extension of the Motzkin-Straus theorem to non-uniform hypergraphs and its applications
- Connection between the clique number and the Lagrangian of 3-uniform hypergraphs
- Homogeneous multilinear functions on hypergraph cliques
- On graph-Lagrangians of hypergraphs containing dense subgraphs
- The connection between polynomial optimization, maximum cliques and Turán densities
- Maximum cliques of hypergraphs and polynomial optimization
- A generalization of the Motzkin-Straus theorem to hypergraphs
- Stability and Turán Numbers of a Class of Hypergraphs via Lagrangians
- Model-order reduction ofkth order MIMO dynamical systems using blockkth order Krylov subspaces
- Connection between polynomial optimization and maximum cliques of non-uniform hypergraphs
- On graph-Lagrangians and clique numbers of 3-uniform hypergraphs
- Lagrangians of hypergraphs: the Frankl-Füredi conjecture holds almost everywhere
- A note on the rationality of \(L\)-functions on finite unoriented graphs
- On cliques and Lagrangians of hypergraphs
- A Motzkin-Straus type result for 3-uniform hypergraphs
- Some results on Lagrangians of hypergraphs
- The eigenvectors to the \(p\)-spectral radius of general hypergraphs
- On finding Lagrangians of 3-uniform hypergraphs.
- The Hessian matrix of Lagrange function
- Lagrangians of Hypergraphs
- On Motzkin-Straus type results for non-uniform hypergraphs
Uses Software
This page was built for publication: On Lagrangians of \(r\)-uniform hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q498456)
