Back to search

University of Waterloo

Quantum independence and chromatic numbers

Abstract

dc:description.abstract

In this thesis we are studying the cases when quantum independence and quantum chromatic numbers coincide with or differ from their classical counterparts. Knowing about the relation of chromatic numbers separation to the projective Kochen-Specker sets, we found an analogous characterisation for the independence numbers case. Additionally, all the graphs that we studied that had known quantum parameters exhibited both the separation between the classical and quantum independence numbers and the separation between the classical and quantum chromatic numbers. This observation and the Kochen-Specker connection suggested the possibility of the chromatic and independence numbers separations occurring simultaneously. We have disproved this idea with a counterexample. Furthermore, we generalised Manĉinska-Roberson’s example of the chromatic numbers separation to an infinite family. We investigate some known instances with strictly larger quantum independence numbers in-depth, find a more general description and generalise Piovesan’s example. Using the Lovász theta bound, we prove that there is no separation between the independence numbers in bipartite and perfect graphs. We also show that there is no separation when the classical independence number is two; and that the cone over a graph has the same quantum independence number as the underlying graph.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sobchuk, Mariia
Advisor dc:contributor.advisor
  • Godsil, Chris

Subjects

dc:subject × 11

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/14980

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Sobchuk, Mariia. Quantum independence and chromatic numbers. University of Waterloo, 2019. http://hdl.handle.net/10012/14980