Geodesic
Conic formulations of graph homomorphisms
Journal of Algebraic Combinatorics, Tome 43 (2016) no. 4, pp. 877-913.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

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.
Classification : 05C85, 05C60
Keywords: conic programming, homomorphisms, quantum information 
@article{JAC_2016__43_4_a1,
     author = {Roberson, David E.},
     title = {Conic formulations of graph homomorphisms},
     journal = {Journal of Algebraic Combinatorics},
     pages = {877--913},
     publisher = {mathdoc},
     volume = {43},
     number = {4},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_2016__43_4_a1/}
}
TY  - JOUR
AU  - Roberson, David E.
TI  - Conic formulations of graph homomorphisms
JO  - Journal of Algebraic Combinatorics
PY  - 2016
SP  - 877
EP  - 913
VL  - 43
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_2016__43_4_a1/
LA  - en
ID  - JAC_2016__43_4_a1
ER  - 
%0 Journal Article
%A Roberson, David E.
%T Conic formulations of graph homomorphisms
%J Journal of Algebraic Combinatorics
%D 2016
%P 877-913
%V 43
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_2016__43_4_a1/
%G en
%F JAC_2016__43_4_a1
Roberson, David E. Conic formulations of graph homomorphisms. Journal of Algebraic Combinatorics, Tome 43 (2016) no. 4, pp. 877-913. http://geodesic.mathdoc.fr/item/JAC_2016__43_4_a1/