David E. Roberson

Research Associate,

My Google Scholar citations.

My most frequent collaborator Laura Mančinska's website.


    email: <first name><middle initial><last name>@gmail.com
    address: University College London
                    Faculty of Engineering Science
                    Department of Computer Science
                    66 Gower Street, London WC1E 6BT

Research Interests

My research primarily focuses on graph theory, in particular homomorphisms. This includes the study of cores, chromatic number and variants such as the Lovász theta number, the homomorphism order of graphs, and unique vector colorings.
I also have an interest in some aspects of quantum information such as nonlocal games and zero-error communication.
I have combined these interests through the introduction and study of quantum homomorphisms.


200– 2013
        Ph.D. in Mathematics
        University of Waterloo
        Advisor: Chris Godsil

200– 2008
        Master of Mathematics
        University of Waterloo
        Advisor: Chris Godsil
        Thesis: The Graphs of Häggkvist and Hell

2003 – 2007
        B.S. in Mathematics
        North Carolina State University

Work in Progress
  • Cores of Cubelike Graphs. Laura Mančinska, Irene Pivotto, David E. Roberson, Gordon Royle.
  • Semidefinite Relaxations of Quantum Graph Isomorphism. Laura Mančinska, David E. Roberson, and Antonios Varvitsiotis.
  • Vector Colorings of Categorical Products. Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, and Antonios Varvitsiotis.

  • Quantum and Non-Signalling Graph Isomorphisms. Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis, 2016. arXiv:1611.09837
  • Graph Homomorphisms via Vector Colorings. Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, and Antonios Varvitsiotis. Submitted to the SIAM Journal on Discrete Mathematics, 2016. arXiv:1610.10002
  • Homomorphisms of Strongly Regular Graphs. David E. Roberson. Submitted to Transactions of the American Mathematical Society, 2016. arXiv:1601.00969
  • Universal completability, least eigenvalue frameworks, and vector colorings. Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, and Antonios Varvitsiotis. Submitted to Discrete & Computational Geometry, 2015. arXiv:1512.04972



Here are some short notes I have written for myself and/or others. They may contain errors and typos and be missing references or complete explanations.
  • Parameter Collapse - This note is primarily about comparing three graph parameters: the Lovasz theta function, a variant of theta recently defined by Laurent and Piovesan, and the projective packing number (defined in my PhD thesis). For a fixed graph the values of these parameters are monotonically nonincreasing with respect to their order in the list above. Interestingly, we show that if the first two parameters are equal on a given graph, then they are all equal.
  • Quantum Correlations and the Completely Positive Semidefinite Cone Here we show a correspondence between the set of two-party quantum correlations and the completely positive semidefinite cone, recently defined by Laurent and Piovesan. In particular, we show that if the completely positive semidefinite cone is closed, then so is the set of two-party quantum correlations.