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á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.
Similar content being viewed by others
References
Laurent, M., Piovesan, T.: Approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone. SIAM J. Optim. 25(4), 2461–2493 (2015). doi:10.1137/14097865X
Feige, U., Lovász, L.: Two-prover one-round proof systems: their power and their problems (extended abstract). In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing. STOC ’92. Victoria, British Columbia, Canada: ACM, pp. 733–744. (1992). doi:10.1145/129712.129783
Bačík, R., Mahajan, S.: Semidefinite programming and its applications to NP problems. English. In: Du, D.-Z., Li, M. (eds.) Computing and Combinatorics, vol. 959. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, pp. 566–575. (1995). doi:10.1007/BFb0030878
Cubitt, T., Mančinska, L., Roberson, D.E., Severini, S., Stahlke, D., Winter, A.: Bounds on entanglement-assisted source-channel coding via the Lovász theta number and its variants. IEEE Trans. Inf. Theory 60(11), 7330–7344 (2014). doi:10.1109/TIT.2014.2349502
Dukanovic, I., Rendl, F.: Copositive programming motivated bounds on the stability and the chromatic numbers. Math. Program. 121(2), 249–268 (2010). doi:10.1007/s10107-008-0233-x
de Klerk, E., Pasechnik, D.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875–892 (2002). doi:10.1137/S1052623401383248
Mančinska, L., Roberson, D.E.: Quantum homomorphisms. J. Comb. Theory Series B (2014). http://www.sciencedirect.com/science/article/pii/S0095895615001550
Roberson, D.E.: Variations on a theme: graph homomorphisms. PhD thesis, University of Waterloo (2013)
Buhrman, H., Cleve, R., Wigderson, A.: Quantum vs. classical communication and computation. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. STOC ’98. Dallas, Texas, United States: ACM, pp. 63–68 (1998). doi:10.1145/276698.276713. eprint:quant-ph/9802040
Galliard, V., Wolf, S.: Pseudo-telepathy, entanglement, and graph colorings. In: IEEE International Symposium on Information Theory. p. 101 (2002). doi:10.1109/ISIT.2002.1023373
Avis, D., Hasegawa, J., Kikuchi, Y., Sasaki, Y.: A quantum protocol to win the graph colouring game on all Hadamard graphs. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E89–A(5), 1378–1381 (2006). doi:10.1093/ietfec/e89-a.5.1378
Frankl, P., Rödl, V.: Forbidden intersections. Trans. Am. Math. Soc. 300(1), 259–286 (1987). doi:10.2307/2000598
Cameron, P.J., Montanaro, A., Newman, M.W., Severini, S., Winter, A.: On the quantum chromatic number of a graph. Electr. J. Comb. 14(1) (2007)
Nayak, J., Tuncel, E., Rose, K.: Zero-error source-channel coding with side information. IEEE Trans. Inf. Theory 52(10), 4626–4629 (2006). doi:10.1109/TIT.2006.881718
Briët, J., Buhrman, H., Laurent, M., Piovesan, T., Scarpa, G.: Zeroerror source-channel coding with entanglement. In: Nešetřil, J., Pellegrini, M. (eds.) The Seventh European Conference on Combinatorics, Graph Theory and Applications, vol. 16. CRM Series. Scuola Normale Superiore, pp. 157–162 (2013). doi:10.1007/978-88-7642-475-5_26
Barioli, F.: Chains of dog-ears for completely positive matrices. Linear Algebra Appl 330(1–3), 49–66 (2001). doi:10.1016/S0024-3795(01)00256-7
Stahlke, D.: Private communication. (2013)
Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25(1), 1–7 (1979). doi:10.1109/TIT.1979.1055985
Knuth, D.E.: The sandwich theorem. Electron. J. Comb. 1, 1 (1994)
Piovesan, T., Scarpa, G., Schaffner, C.: Multiparty zero-error classical channel coding with entanglement. IEEE Trans. Inf. Theory 61(2), 1113–1123 (2015). doi:10.1109/TIT.2014.2379273
Mančinska, L., Roberson, D.E.: Note on the correspondence between quantum correlations and the completely positive semidefinite cone. (2014). http://quantuminfo.quantumlah.org/memberpages/laura/corr.pdf
Acknowledgments
D. E. Roberson is supported in part by the Singapore National Research Foundation under NRF RF Award No. NRF-NRFF2013-13.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Roberson, D.E. Conic formulations of graph homomorphisms. J Algebr Comb 43, 877–913 (2016). https://doi.org/10.1007/s10801-016-0665-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10801-016-0665-y