Mančinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if and only if they are homomorphism indistinguishable over the class of planar graphs. Atserias et al. [JCTB'19] proved that quantum isomorphism is undecidable in general. The NPA hierarchy gives a sequence of semidefinite programming relaxations of quantum isomorphism. Recently, Roberson and Seppelt [ICALP'23] obtained a homomorphism indistinguishability characterization of the feasibility of each level of the Lasserre hierarchy of semidefinite programming relaxations of graph isomorphism. We prove a quantum analogue of this result by showing that each level of the NPA hierarchy of SDP relaxations for quantum isomorphism of graphs is equivalent to homomorphism indistinguishability over an appropriate class of planar graphs. By combining the convergence of the NPA hierarchy with the fact that the union of these graph classes is the set of all planar graphs, we are able to give a new proof of the result of Mančinska and Roberson [FOCS'20] that avoids the use of the theory of quantum groups. This homomorphism indistinguishability characterization also allows us to give a randomized polynomial-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism.

The minimum rank of a graph G is the minimum of the ranks of all symmetric adjacency matrices of G. We present a new combinatorial bound for the minimum rank of an arbitrary graph G based on enumerating certain subsets of vertices of G satisfying matroid theoretic properties. We also present some computational and theoretical challenges associated with computing the minimum rank. This includes a conjecture that this bound on the minimum rank actually holds with equality for all graphs. History: This “Challenge” paper was invited by the Editor in Chief and based on the topics raised by the author at his plenary address at the 2022 INFORMS Computing Society Conference in Tampa, Florida. Funding: This work was supported by the National Science Foundation [Grant DMS-1720225]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.1219 .

Over 50 years ago, Lovász proved that two graphs are isomorphic if and only if they admit the same number of homomorphisms from any graph. Other equivalence relations on graphs, such as cospectrality or fractional isomorphism, can be characterized by equality of homomorphism counts from an appropriately chosen class of graphs. Dvořák [J. Graph Theory 2010] showed that taking this class to be the graphs of treewidth at most k yields a tractable relaxation of graph isomorphism known as k-dimensional Weisfeiler-Leman equivalence. Together with a famous result of Cai, Fürer, and Immerman [FOCS 1989], this shows that homomorphism counts from graphs of bounded treewidth do not determine a graph up to isomorphism. Dell, Grohe, and Rattan [ICALP 2018] raised the questions of whether homomorphism counts from planar graphs determine a graph up to isomorphism, and what is the complexity of the resulting relation. We answer the former in the negative by showing that the resulting relation is equivalent to the so-called quantum isomorphism [Mančinska et al, ICALP 2017]. Using this equivalence, we further resolve the latter question, showing that testing whether two graphs have the same number of homomorphisms from any planar graph is, surprisingly, an undecidable problem, and moreover is complete for the class coRE (the complement of recursively enumerable problems). Quantum isomorphism is defined in terms of a one-round, two-prover interactive proof system in which quantum provers, who are allowed to share entanglement, attempt to convince the verifier that the graphs are isomorphic. Our combinatorial proof leverages the quantum automorphism group of a graph, a notion from noncommutative mathematics.

We introduce a nonlocal game that captures and extends the notion of graph isomorphism. This game can be won in the classical case if and only if the two input graphs are isomorphic. Thus, by considering quantum strategies we are able to define the notion of quantum isomorphism. We also consider the case of more general non-signalling strategies, and show that such a strategy exists if and only if the graphs are fractionally isomorphic. We prove several necessary conditions for quantum isomorphism, including cospectrality, and provide a construction for producing pairs of non-isomorphic graphs that are quantum isomorphic. We then show that both classical and quantum isomorphism can be reformulated as feasibility programs over the completely positive and completely positive semidefinite cones respectively. This leads us to considering relaxations of (quantum) isomorphism arrived at by relaxing the cone to either the doubly nonnegative (DNN) or positive semidefinite (PSD) cones. We show that DNN-isomorphism is equivalent to the previous defined notion of graph equivalence, a polynomial-time decidable relation that is related to coherent algebras. We also show that PSD-isomorphism implies several types of cospectrality, and that it is equivalent to cospectrality for connected 1-walk-regular graphs. Finally, we show that all of the above mentioned relations form a strict hierarchy of weaker and weaker relations, with non-singalling/fractional isomorphism being the weakest. The techniques used are an interesting mix of algebra, combinatorics, and quantum information.

An embedding $$i \mapsto p_i\in \mathbb {R}^d$$ of the vertices of a graph G is called universally completable if the following holds: For any other embedding $$i\mapsto q_i~\in \mathbb {R}^{k}$$ satisfying $$q_i^{T}q_j = p_i^{T}p_j$$ for $$i = j$$ and i adjacent to j, there exists an isometry mapping $$q_i$$ to $$p_i$$ for all $$ i\in V(G)$$ . The notion of universal completability was introduced recently due to its relevance to the positive semidefinite matrix completion problem. In this work we focus on graph embeddings constructed using the eigenvectors of the least eigenvalue of the adjacency matrix of G, which we call least eigenvalue frameworks. We identify two necessary and sufficient conditions for such frameworks to be universally completable. Our conditions also allow us to give algorithms for determining whether a least eigenvalue framework is universally completable. Furthermore, our computations for Cayley graphs on $$\mathbb {Z}_2^n \ (n \le 5)$$ show that almost all of these graphs have universally completable least eigenvalue frameworks. In the second part of this work we study uniquely vector colorable (UVC) graphs, i.e., graphs for which the semidefinite program corresponding to the Lovász theta number (of the complementary graph) admits a unique optimal solution. We identify a sufficient condition for showing that a graph is UVC based on the universal completability of an associated framework. This allows us to prove that Kneser and q-Kneser graphs are UVC. Lastly, we show that least eigenvalue frameworks of 1-walk-regular graphs always provide optimal vector colorings and furthermore, we are able to characterize all optimal vector colorings of such graphs. In particular, we give a necessary and sufficient condition for a 1-walk-regular graph to be uniquely vector colorable.

We study zero-error entanglement-assisted source-channel coding (communication in the presence of side information). Adapting a technique of Beigi, we show that such coding requires existence of a set of vectors satisfying orthogonality conditions related to suitably defined graphs G and H. Such vectors exist if and only if ϑ(G̅) ≤ ϑ(H̅), where ϑ represents the Lovász number. We also obtain similar inequalities for the related Schrijver ϑ-and Szegedy ϑ+numbers. These inequalities reproduce several known bounds and also lead to new results. We provide a lower bound on the entanglement-assisted cost rate. We show that the entanglement-assisted independence number is bounded by the Schrijver number: α*(G) ≤ ϑ-(G). Therefore, we are able to disprove the conjecture that the one-shot entanglement-assisted zero-error capacity is equal to the integer part of the Lovász number. Beigi introduced a quantity β as an upper bound on α* and posed the question of whether β(G) = ⌊ϑ(G)⌋. We answer this in the affirmative and show that a related quantity is equal to ⌊ϑ(G)⌋. We show that a quantity χvect(G) recently introduced in the context of Tsirelson's problem is equal to ⌊ϑ+(G)⌋. In an appendix, we investigate multiplicativity properties of Schrijver's and Szegedy's numbers, as well as projective rank.