David E. Roberson

Ørsted Fellow
Algorithms, Logic, and Graph Theory (AlgoLoG)

I am currently investigating the connection between quantum groups and quantum information provided by our notion of quantum isomorphisms of graphs. This is part of my project Quantum Isomorphisms: A Bridge between Quantum Groups and Quantum Information, for which I was awarded an H.CØrsted Fellowship. The position is funded by the Marie Skłodowska-Curie COFUND.


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

Research Interests

My two primary research areas are graph theory and quantum information. Within graph theory I am interested in homomorphisms, chromatic number and variants such as the Lovász theta number, and relaxations of graph isomorphism. I often employ algebraic tools and techniques in my work in graph theory. My research in quantum information is mainly focused on nonlocal games and zero-error communication. I have combined my interests in graph theory and quantum information through the introduction and study of quantum homomorphisms and isomorphisms.

Employment History

Feb 2018 – Dec 2018
        Department of Physics
        Technical University of Denmark

Sep 2017  Jan 2018
        Department of Applied Mathematics and Computer Science
        Technical University of Denmark

Dec 2015  Dec 2016
        Research Associate
        Department of Computer Science
        University College London

Oct 2014 – Nov 2015
        Postdoctoral Research Fellow
        Centre for Quantum Technologies

Oct 2013 – Oct 2014
        Postdoctoral Research Fellow
        Division of Mathematical Sciences
        Nanyang Technological University


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
  • Independent Sets in Gallai Graphs. Krystal Guo and David E. Roberson
  • Endomorphisms in 3-Class Association Schemes. Chris Godsil, David E. Roberson, & Brendan Rooney.
  • Semidefinite Relaxations of (Quantum) Graph Isomorphism. Laura Mančinska, David E. Roberson, and Antonios Varvitsiotis.


25. Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. Laura Mančinska and David E. Roberson. arXiv:1910.06958

24. Cores of Cubelike Graphs. Laura Mančinska, Irene Pivotto, David E. Roberson, and Gordon Royle. Under revision at European Journal of Combinatorics, 2018. arXiv:1808.02051

23. Nonlocal Games and Quantum Permutation Groups. Martino Lupini, Laura Mančinska, and David E. Roberson. Submitted to Journal of Functional Analysis, 2019. arXiv:1712.01820

22. 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. Accepted to Mathematical Physics, Analysis and Geometry, 2019. arXiv:1804.06151

21. Vector Coloring the Categorical Product of Graphs. Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, and Antonios Varvitsiotis. Mathematical Programming, 2019. arXiv:1801.08243

20. Algebras, Graphs, and Thetas. Marcel K. de Carli Silva, Gabriel Coutinho, Chris Godsil, and David E. Roberson. Electronic Notes in Theoretical Computer Science, 346:275–283, 2019arXiv:1910.06260

19. Graph Homomorphisms via Vector Colorings. Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, and Antonios Varvitsiotis. European Journal of Combinatorics, 79:244–261, 2019arXiv:1610.10002

18. Homomorphisms of Strongly Regular Graphs. David E. Roberson. Algebraic Combinatorics, 2(4):481497, 2019. arXiv:1601.00969

17. Quantum and Non-Signalling Graph Isomorphisms. Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis. Journal of Combinatorial Theory, Series B, 136:289328, 2019. arXiv:1611.09837

16. Relaxations of Graph Isomorphism. Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis. Leibniz International Proceedings in Informatics (LIPIcs), 80, 2017. Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017).

15. Universal completability, least eigenvalue frameworks, and vector colorings. Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, and Antonios Varvitsiotis. Discrete & Computational Geometry, 58(2):265292, 2017. arXiv:1512.04972

14. Note on von Neumann and Rényi entropies of a graph. Michael Dairyko, Leslie Hogben, Jephian C.-H. Lin, Joshua Lockhart, David E. Roberson, Simone Severini, Michael Young. Linear Algebra and its Applications, 521:240–2532017. arXiv:1609.00420

13. Orthogonal Representations, Projective Rank, and Fractional Minimum Positive Semidefinite Rank: Connections and New Directions. Leslie Hogben, Kevin F. Palmowski, David E. Roberson, and Simone Severini. Electronic Journal of Linear Algebra, 32:98–115, 2017. arXiv:1502.00016

12. Sabidussi versus Hedetniemi for Three Variations of Chromatic Number. Chris Godsil, David E. Roberson, Robert Šámal, and Simone Severini. Combinatorica, 36(4):395415, 2016. arXiv:1305.5545

11. Oddities of Quantum Colorings. Laura Mančinska and  David E. Roberson. Baltic Journal of Modern Computing, 4(4):846859, 2016. arXiv:1801.03542

10. Conic Formulations of Graph Homomorphisms. David E. Roberson. Journal of Algebraic Combinatorics, 43(4):877913, 2016. arXiv:1411.6723

9. Fractional Zero Forcing via Three-color Forcing Games. Leslie Hogben, Kevin F. Palmowski, David E. Roberson, and Michael Young. Discrete Applied Mathematics, 213(20):114–129, 2016arXiv:1509.02883

8. On deciding the existence of perfect entangled strategies for nonlocal games. Laura Mančinska, David E. Roberson, and Antonios Varvitsiotis. Chicago Journal of Theoretical Computer Science, 2016. arXiv:1506.07429

7. Quantum Homomorphisms. Laura Mančinska and David E. Roberson. Journal of Combinatorial Theory, Series B118:228–267, 2016. Presented as a highlighted talk at the 9th Conference on the Theory of Quantum Computation and Cryptography, 2014. arXiv:1212.1724

6. A new property of the Lovász theta function and duality relations between graph parameters. Antonio Acín, Runyao Duan, David E. Roberson, Ana Belén Sainz, Andreas Winter. Discrete Applied Mathematics, 216(3):489–501, 2016. arXiv:1505.01265

5. Graph Cores via Universal Completability. Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, and Antonios Varvitsiotis. Electronic Notes in Combinatorics, 49:337344, 2015. Proceedings of Eurocomb '15.

4. Bounds on Entanglement Assisted Source-Channel Coding via the Lovasz Theta Number and its Variants. Toby Cubitt, Laura Mančinska, David E. Roberson, Simone Severini, Dan Stahlke, and Andreas Winter. IEEE Transactions on Information Theory, 60(11):73307344, 2014. arXiv:1310.7120

3. Two Characterizations of Nonlocal Games with Perfect Maximally Entangled Strategies. Laura Mančinska, David E. Roberson, and Antonios Varvitsiotis. Proceedings of the 14th Asian Quantum Information Science Conference (AQIS'14).

2. Cores of Vertex Transitive Graphs. David E. Roberson. The Electronic Journal of Combinatorics20(2):P45, 2013. arXiv:1302.4470

1. Häggkvist-Hell Graphs: A Class of Kneser-colorable Graphs. David E. Roberson. Discrete Mathematics, 312(5):837853, 2012. arXiv:1008.2199


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.

Strange Behaviour

The graph below has both chromatic number and quantum chromatic number equal to four. However, if a new vertex adjacent to all other vertices is added, then the chromatic number goes up by one but the quantum chromatic number remains four. This is unusual behaviour in comparison to many other chromatic number type parameters. This also gives the smallest known graph with a separation between chromatic and quantum chromatic numbers. Find out more here: Oddities of quantum colorings.