We prove RE-completeness of the quantum homomorphism problem parameterised by families of graphs derived from the classic metric association schemes. These include Kneser graphs, $q$-Kneser graphs, and the complements of Johnson, Grassmann, and Hamming graphs. Our proof develops a spectral method for establishing non-contextuality of quantum polymorphisms. It combines an equality analysis of Roberson's bound on the projective packing number in terms of Schrijver's theta with a structural argument inspired by Erd\H{o}s-Ko-Rado theory.
We study the quantum Cayley graphs associated with the Kac-Paljutkin quantum group. We determine which projections give rise to undirected, irreflexive and connected quantum graphs and classify them up to isomorphism. Their spectra and chromatic numbers are computed. For the special case of the projection $p = I_2$ we...
We use a Gröbner basis technique first introduced by Knutson, Miller and Yong to study the interplay between properties of a graph [Formula: see text] and algebraic properties of the toric ideal that it defines. We first recover a well-known height formula for the toric ideal of a graph [Formula: see text] and demonstr...
Sergio Da Silva, Emma Naguit, Jenna Rajchgot· Journal of Algebra and its A...· 0 citations
We establish a general structure theorem for local quantum Cuntz--Krieger families associated to finite quantum graphs whose relations are analogous to those of the partial isometries generating an ordinary graph $C^*$-algebra, with the quantum edge correspondence governing composition. We apply this structure theorem...
Which vertex-transitive graphs of prime order have quantum symmetry? The question of Banica, Bichon and Chenevier is open in the dense regime of Paley graphs, where coherent-algebra methods give no information. To each such graph we attach a two-basepoint Terwilliger algebra of its cyclotomic scheme and study the modul...
We construct a family of finite local rings whose annihilating-ideal graphs are naturally described by orthogonality of subspaces of $\mathbb{F}_2^n$. For $n=4$ we determine the clique and chromatic numbers exactly and obtain \[ \omega(\AG(R_4))=5<6=\chi(\AG(R_4)). \] Thus $\AG(R_4)$ is not weakly perfect, and the Behb...
R. Nikandish· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.