70 citations · 271 across the 35 of their papers we have counts for
7 papers · 1 filter
Graph isomorphism: Physical resources, optimization models, and algebraic characterizations
Laura Mančinska, David E. Roberson, Antonios Varvitsiotis
In the -isomorphism game, a verifier interacts with two non-communicating players (called provers) by privately sending each of them a random vertex from either or ,…
Vector Coloring the Categorical Product of Graphs
Chris Godsil, David E. Roberson, Brendan Rooney +2
A vector -coloring of a graph is an assignment of real vectors to its vertices such that for all and whene…
Graph Homomorphisms via Vector Colorings
Chris Godsil, David E. Roberson, Brendan Rooney +2
In this paper we study the existence of homomorphisms using semidefinite programming. Specifically, we use the vector chromatic number of a graph, defined as the smallest…
Universal completability, least eigenvalue frameworks, and vector colorings
Chris Godsil, David E. Roberson, Brendan Rooney +2
An embedding of the vertices of a graph is called universally completable if the following holds: For any other embedding $i\mapsto q_i~\in \mat…
Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope
Marianna Eisenberg-Nagy, Monique Laurent, Antonios Varvitsiotis
We study a new geometric graph parameter $\egd(G)$, defined as the smallest integer for which any partial symmetric matrix which is completable to a correlation matrix and…
The Gram dimension of a graph
Monique Laurent, Antonios Varvitsiotis
The Gram dimension $\gd(G)$ of a graph is the smallest integer such that, for every assignment of unit vectors to the nodes of the graph, there exists another assignment…