{"id":"arxiv/2605.19543","url":"https://arxiv.org/abs/2605.19543","tags":["math.CO"],"score":0,"title":"The Quantum Homomorphism Orders are Universal","domain":"math.CO","source":"arxiv","authors":["Yangjing Long"],"reviews":0,"subject":"math.CO","summary":"Quantum graph homomorphisms, introduced by Mančinska and Roberson, form a natural quantum relaxation of classical graph homomorphisms. Since this relaxation may create new comparabilities, it could in principle collapse antichains and other order-theoretic configurations. We prove that this does not happen: the quantum homomorphism quasi-order of finite directed graphs is countably universal, and the quantum homomorphism quasi-order of finite planar graphs of maximum degree at most $7$ is also countably universal. Consequently, the same universality holds for finite undirected graphs and for…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-19","reactions":{}}