P. Wocjan

activity

20002026

most citedSampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer

211 citations · 1.2k across the 74 of their papers we have counts for

collaborators

Showing math.COShow all

16 papers · 1 filter

math.CO2021★ 2 cited

Two conjectured strengthenings of Turán's theorem

Clive Elphick, William Linz, Pawel Wocjan

We investigate two conjectured spectral graph theoretic strengthenings of Turán's theorem. Let $μ_{1} \geq \dots \geq μ_{n}$ denote the eigenvalues of a graph $G$ with $n$ vertices, $m$ …

math.CO2019★ 1 cited

Spectral upper bound on the quantum k-independence number of a graph

Pawel Wocjan, Clive Elphick, Aida Abiad

A well known upper bound for the independence number $α (G)$ of a graph $G$ , due to Cvetković, is that \begin{equation*} α(G) \le n^0 + \min\{n^+ , n^-\} \end{equation*} where $(n^+…

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★ 1 cited

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★ 1 cited

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★ 2 cited

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…

math.CO2017

Conjectured bound for the distribution of eigenvalues of a graph

Pawel Wocjan, Clive Elphick

Let $(n^{+}, n^{0}, n^{-})$ denote the inertia of a graph $G$ with $n$ vertices. Nordhaus-Gaddum bounds are known for inertia, except for an upper bound for $n^{-}$ . We conjecture that for…

math.CO2016

An inertial lower bound for the chromatic number of a graph

Clive Elphick, Pawel Wocjan

Let $χ (G$ ) and $χ_{f} (G)$ denote the chromatic and fractional chromatic numbers of a graph $G$ , and let $(n^{+}, n^{0}, n^{-})$ denote the inertia of $G$ . We prove that: \[ 1 + \max\left…

math.CO2015★ 1 cited

Bounds and power means for the general Randic index

Clive Elphick, Pawel Wocjan

We review bounds for the general Randić index, $R_{α} = \sum_{ij \in E} (d_{i} d_{j})^{α}$ , and use the power mean inequality to prove, for example, that $R_{α} \geq m λ^{2 α}$ for $α < 0$ , where…

math.CO2014★ 1 cited

Conjectured bounds for the sum of squares of positive eigenvalues of a graph

Clive Elphick, Felix Goldberg, Miriam Farber +1

A well known upper bound for the spectral radius of a graph, due to Hong, is that $μ_{1}^{2} \leq 2 m - n + 1$ . It is conjectured that for connected graphs $n - 1 \leq s^{+} \leq 2 m - n + 1$ …

math.CO2013

New measures of graph irregularity

Clive Elphick, Pawel Wocjan

In this paper, we define and compare four new measures of graph irregularity. We use these measures to prove upper bounds for the chromatic number and the Colin de Verdiere paramet…

math.CO2012★ 4 cited

On the Probability of Generating a Lattice

Felix Fontein, Pawel Wocjan

We study the problem of determining the probability that m vectors selected uniformly at random from the intersection of the full-rank lattice L in R^n and the window [0,B)^n gener…

math.CO2012

Unified spectral bounds on the chromatic number

Clive Elphick, Pawel Wocjan

One of the best known results in spectral graph theory is the following lower bound on the chromatic number due to Alan Hoffman, where mu_1 and mu_n are respectively the maximum an…

math.CO2012

New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix

Pawel Wocjan, Clive Elphick

The purpose of this article is to improve existing lower bounds on the chromatic number chi. Let mu_1,...,mu_n be the eigenvalues of the adjacency matrix sorted in non-increasing o…