Conic formulations of graph homomorphisms

详细信息    查看全文

• 作者：David E. Roberson
• 刊名：Journal of Algebraic Combinatorics
• 出版年：2016
• 出版时间：June 2016
• 年：2016
• 卷：43
• 期：4
• 页码：877-913
• 全文大小：631 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Order, Lattices and Ordered Algebraic Structures
  Computer Science, general
  Group Theory and Generalizations
  
• 出版者：Springer U.S.
• ISSN：1572-9192
• 卷排序：43

文摘

Given graphs X and Y, we define two conic feasibility programs which we show have a solution over the completely positive cone if and only if there exists a homomorphism from X to Y. By varying the cone, we obtain similar characterizations of quantum/entanglement-assisted homomorphisms and three previously studied relaxations of these relations. Motivated by this, we investigate the properties of these “conic homomorphisms” for general (suitable) cones. We also consider two generalized versions of the Lovász theta function, and how they interact with these conic homomorphisms. We prove analogs of several results on classical graph homomorphisms as well as some monotonicity theorems. We also show that one of the generalized theta functions is multiplicative on lexicographic and disjunctive graph products.KeywordsGraph theoryConic programmingHomomorphisms Quantum information