David E. Roberson

Quantum Physics and Information Technology (QPIT)

My Google Scholar citations.

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


    email: <first name><middle initial><last name>@gmail.com
    address: DTU Compute
                    Richard Petersens Plads
                    Building 322
                    DK-2800 Kgs. Lyngby

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 and isomorphisms.


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, and Gabriel Verret.
  • Semidefinite Relaxations of (Quantum) Graph Isomorphism. Laura Mančinska, David E. Roberson, and Antonios Varvitsiotis.

  • Perfect Strategies for Non-signalling Games. Martino Lupini, Laura Mančinska, Vern Paulsen, David E. Roberson, Giannicola Scarpa, Simone Severini, Ivan Todorov, and Andreas Winter. Submitted to Communications in Mathematical Physics, 2018. arxiv:1804.06151
  • Vector Coloring the Categorical Product of Graphs. Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, and Antonios Varvitsiotis. Submitted to Mathematical Programming, 2018. arXiv:1801.08243
  • Nonlocal Games and Quantum Permutation Groups. Martino Lupini, Laura Mančinska, and David E. Roberson. Submitted to Communications in Mathematical Physics, 2018. arXiv:1712.01820
  • Quantum and Non-Signalling Graph Isomorphisms. Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis. Submitted to the Journal of Combinatorial Theory, Series B, 2017. arXiv:1611.09837
  • Graph Homomorphisms via Vector Colorings. Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, and Antonios Varvitsiotis. Submitted to the European Journal of Combinatorics, 2018arXiv:1610.10002
  • Homomorphisms of Strongly Regular Graphs. David E. Roberson. Submitted to Algebraic Combinatorics, 2017. arXiv:1601.00969



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.