C. Elphick

activity

20122019

collaborators

7 papers

math.CO2019

Spectral Lower Bounds for the Quantum Chromatic Number of a Graph -- Part II

Pawel Wocjan, Clive Elphick, Parisa Darbari

Hoffman proved that a graph $G$ with eigenvalues $μ_{1} \geq \dots \geq μ_{n}$ and chromatic number $χ (G)$ satisfies: \[ χ\ge 1 + κ\] where $κ$ is the smallest integer such that \[ μ_1…

math.CO2018

More Tales of Hoffman: bounds for the vector chromatic number of a graph

Pawel Wocjan, Clive Elphick, David Anekstein

Let $χ (G)$ denote the chromatic number of a graph and $χ_{v} (G)$ denote the vector chromatic number. For all graphs $χ_{v} (G) \leq χ (G)$ and for some graphs $χ_{v} (G) ≪ χ (G)$ . Galtman p…

math.CO2018

An inertial upper bound for the quantum independence number of a graph

Pawel Wocjan, Clive Elphick

A well known upper bound for the independence number $α (G)$ of a graph $G$ , is that \[ α(G) \le n^0 + \min\{n^+ , n^-\}, \] where $(n^{+}, n^{0}, n^{-})$ is the inertia of $G$ . We prove…

math.CO2018

Spectral lower bounds for the orthogonal and projective ranks of a graph

Pawel Wocjan, Clive Elphick

The orthogonal rank of a graph $G = (V, E)$ is the smallest dimension $ξ$ such that there exist non-zero column vectors $x_{v} \in C^{ξ}$ for $v \in V$ satisfying the orthogonality…

math.CO2018

Spectral lower bounds for the quantum chromatic number of a graph

Pawel Wocjan, Clive Elphick

The quantum chromatic number, $χ_{q} (G)$ , of a graph $G$ was originally defined as the minimal number of colors necessary in a quantum protocol in which two provers that cannot commu…

math.CO2018

Conjectured lower bound for the clique number of a graph

Clive Elphick, Pawel Wocjan

It is well known that $n / (n - μ)$ , where $μ$ is the spectral radius of a graph with $n$ vertices, is a lower bound for the clique number. We conjecture that $μ$ can be replaced in…