Connection between a class of polynomial optimization problems and maximum cliques of non-uniform hypergraphs

Yanming Chang (), Yuejian Peng () and Yuping Yao ()
Additional contact information
Yanming Chang: Hunan University
Yuejian Peng: Hunan University
Yuping Yao: Hunan University

Journal of Combinatorial Optimization, 2016, vol. 31, issue 2, No 27, 892 pages

Abstract: Abstract In 1965, Motzkin and Straus provided a connection between the order of a maximum clique in a graph $$G$$ G and a global solution of a quadratic optimization problem determined by $$G$$ G which is called the Lagrangian function of $$G$$ G . This connection and its extensions have been useful in both combinatorics and optimization. In 2009, Rota Bulò and Pelillo extended the Motzkin–Straus result to $$r$$ r -uniform hypergraphs by establishing a one-to-one correspondence between local (global) minimizers of a family of homogeneous polynomial functions of degree $$r$$ r (different from Lagrangian function) and the maximal (maximum) cliques of an $$r$$ r -uniform hypergraph. In this paper, we study similar optimization problems related to non-uniform hypergraphs and obtain some extensions of their results to non-uniform hypergraphs. In particular, we provide a one-to-one correspondence between local (global) minimizers of a family of non-homogeneous polynomial functions and the maximal (maximum) cliques of $$\{1, r\}$$ { 1 , r } -hypergraphs. An application of a main result gives an upper bound on the Turán density of complete $$\{1, r\}$$ { 1 , r } -hypergraphs. The approach applied in the proof follows from the approach in Rota Bulò and Pelillo (2009).

Keywords: Hypergraph; Maximum clique; Polynomial optimization (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9798-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:31:y:2016:i:2:d:10.1007_s10878-014-9798-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9798-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().