Conic formulations of graph homomorphisms

DOI10.1007/S10801-016-0665-YzbMATH Open1339.05401arXiv1411.6723OpenAlexW1674246975MaRDI QIDQ295829FDOQ295829

Authors: David Roberson 

Publication date: 13 June 2016

Published in: Journal of Algebraic Combinatorics (Search for Journal in Brave)

Abstract: 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'asz 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.

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

Recommendations

• Graphs and irreducible cone preserving maps
• scientific article; zbMATH DE number 3880749
• Realization of homogeneous cones through oriented graphs
• scientific article; zbMATH DE number 2094514
• Homomorphisms and related contractions of graphs
• Convex graph invariants
• Geometric graph homomorphisms
• scientific article; zbMATH DE number 1874377
• On homometric sets in graphs
• On homometric sets in graphs

zbMATH Keywords

quantum informationhomomorphismsconic programming

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• On the quantum chromatic number of a graph
• Forbidden Intersections
• On the Shannon capacity of a graph
• Title not available (Why is that?)
• Approximation of the stability number of a graph via copositive programming
• The sandwich theorem
• Graph homomorphisms for quantum players
• Multiparty Zero-Error Classical Channel Coding With Entanglement
• Bounds on Entanglement-Assisted Source-Channel Coding via the Lovász \(\vartheta \) Number and Its Variants
• Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
• Zero-Error Source–Channel Coding With Side Information
• Chains of dog-ears for completely positive matrices
• Copositive programming motivated bounds on the stability and the chromatic numbers

Cited In (13)

• Correlation matrices, Clifford algebras, and completely positive semidefinite rank
• Quantum homomorphisms
• Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
• Algebras, graphs and thetas
• Title not available (Why is that?)
• Completely positive semidefinite rank
• A compositional approach to quantum functions
• Matrices with high completely positive semidefinite rank
• Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
• Positively factorizable maps
• Dual Hoffman bounds for the stability and chromatic numbers based on semidefinite programming
• Linear conic formulations for two-party correlations and values of nonlocal games
• Graph isomorphism: physical resources, optimization models, and algebraic characterizations

This page was built for publication: Conic formulations of graph homomorphisms

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