BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
David Roberson appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We conjecture that all connected graphs of order $n$ have von Neumann entropy at least as great as the star $K_{1,n-1}$ and prove this for almost all graphs of order $n$. We show that connected graphs of order $n$ have Rényi 2-entropy at least as great as $K_{1,n-1}$ and for $α>1$, $K_n$ maximizes Rényi $α$-entropy over graphs of order $n$. We show that adding an edge to a graph can lower its von Neumann entropy.
We study zero-error entanglement assisted source-channel coding (communication in the presence of side information). Adapting a technique of Beigi, we show that such coding requires existence of a set of vectors satisfying orthogonality conditions related to suitably defined graphs $G$ and $H$. Such vectors exist if and only if $\vartheta(\overline{G}) \le \vartheta(\overline{H})$ where $\vartheta$ represents the Lovász number. We also obtain similar inequalities for the related Schrijver $\vartheta^-$ and Szegedy $\vartheta^+$ numbers. These inequalities reproduce several known bounds and also lead to new results. We provide a lower bound on the entanglement assisted cost rate. We show that the entanglement assisted independence number is bounded by the Schrijver number: $α^*(G) \le \vartheta^-(G)$. Therefore, we are able to disprove the conjecture that the one-shot entanglement-assisted zero-error capacity is equal to the integer part of the Lovász number. Beigi introduced a quantity $β$ as an upper bound on $α^*$ and posed the question of whether $β(G) = \lfloor \vartheta(G) \rfloor$. We answer this in the affirmative and show that a related quantity is equal to $\lceil \vartheta(G) \rceil$. We show that a quantity $χ_{\textrm{vect}}(G)$ recently introduced in the context of Tsirelson's conjecture is equal to $\lceil \vartheta^+(\overline{G}) \rceil$. In an appendix we investigate multiplicativity properties of Schrijver's and Szegedy's numbers, as well as projective rank.
A core of a graph X is a vertex minimal subgraph to which X admits a homomorphism. Hahn and Tardif have shown that for vertex transitive graphs, the size of the core must divide the size of the graph. This motivates the following question: when can the vertex set of a vertex transitive graph be partitioned into sets each of which induce a copy of its core? We show that normal Cayley graphs and vertex transitive graphs with cores half their size always admit such partitions. We also show that the vertex sets of vertex transitive graphs with cores less than half their size do not, in general, have such partitions.
We investigate vector chromatic number, Lovasz theta of the complement, and quantum chromatic number from the perspective of graph homomorphisms. We prove an analog of Sabidussi's theorem for each of these parameters, i.e. that for each of the parameters, the value on the Cartesian product of graphs is equal to the maximum of the values on the factors. We also prove an analog of Hedetniemi's conjecture for Lovasz theta of the complement, i.e. that its value on the categorical product of graphs is equal to the minimum of its values on the factors. We conjecture that the analogous results hold for vector and quantum chromatic number, and we prove that this is the case for some special classes of graphs.
For positive integers n and r we define the Haggkvist-Hell graph, H_{n:r}, to be the graph whose vertices are the ordered pairs (h,T) where T is an r-subset of [n], and h is an element of [n] not in T. Vertices (h_x,T_x) and (h_y,T_y) are adjacent iff h_x \in T_y, h_y \in T_x, and T_x and T_y are disjoint. These triangle-free arc transitive graphs are an extension of the idea of Kneser graphs, and there is a natural homomorphism from the Haggkvist-Hell graph, H_{n:r}, to the corresponding Kneser graph, K_{n:r}. Haggkvist and Hell introduced the r=3 case of these graphs, showing that a cubic graph admits a homomorphism to H_{22:3} if and only if it is triangle-free. Gallucio, Hell, and Nesetril also considered the r=3 case, proving that H_{n:3} can have arbitrarily large chromatic number. In this paper we give the exact values for diameter, girth, and odd girth of all Haggkvist-Hell graphs, and we give bounds for independence, chromatic, and fractional chromatic number. Furthermore, we extend the result of Gallucio et al. to any fixed r \ge 2, and we determine the full automorphism group of H_{n:r}, which is isomorphic to the symmetric group on n elements.