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
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.
2009 – 2013
Ph.D. in Mathematics
University of Waterloo
Advisor: Chris Godsil
2007 – 2008
Master of Mathematics
University of Waterloo
Advisor: Chris Godsil
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
- 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, 2017.
- 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. Accepted to the Electronic Journal of Linear Algebra, 2017. arXiv:1502.00016
- Oddities of Quantum Colorings. Laura Mančinska, David E. Roberson. Baltic Journal of Modern Computing, 2016.
- Fractional Zero Forcing via Three-color Forcing Games. Leslie Hogben, Kevin F. Palmowski, David E. Roberson, and Michael Young. Discrete Applied Mathematics, 2016. arXiv:1509.02883
- Deciding the existence of perfect entangled strategies for nonlocal games. Laura Mančinska, David E. Roberson, and Antonios Varvitsiotis. Accepted to the Chicago Journal of Theoretical Computer Science, 2016. arXiv:1506.07429
- 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, 2016. arXiv:1505.01265
- Quantum Homomorphisms. Laura Mančinska and David E. Roberson. Journal of Combinatorial Theory, Series B, 2016. Presented as a highlighted talk at the 9th Conference on the Theory of Quantum Computation and Cryptography, 2014. arXiv:1212.1724
- Conic Formulations of Graph Homomorphisms. David E. Roberson. Journal of Algebraic Combinatorics, 2016. arXiv:1411.6723
- Graph Cores via Universal Completability. Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, and Antonios Varvitsiotis. Electronic Notes in Discrete Mathematics, 49:337–344, 2015. Proceedings of EuroComb '15.
- Sabidussi versus Hedetniemi for Three Variations of Chromatic Number. Chris Godsil, David E. Roberson, Robert Šámal, Simone Severini. Combinatorica, 2015. arXiv:1305.5545
- 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).
- 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):7330–7344, 2014. arXiv:1310.7120
- Cores of Vertex Transitive Graphs. David E. Roberson. The Electronic Journal of Combinatorics, 20(2):P45, 2013. arXiv:1302.4470
- Häggkvist-Hell Graphs: A Class of Kneser-colorable Graphs. David E. Roberson. Discrete Mathematics, 312(5):837–853, 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.