Back to search

University of Waterloo

Algebraic and combinatorial aspects of incidence groups and linear system non-local games arising from graphs

Abstract

dc:description.abstract

To every linear binary-constraint system (LinBCS) non-local game, there is an associated algebraic object called the solution group. Cleve, Liu, and Slofstra showed that a LinBCS game has a perfect quantum strategy if and only if an element, denoted by $J$, is non-trivial in this group. In this work, we restrict to the set of graph-LinBCS games, which arise from \mathbb{Z}2-linear systems $Ax=b$, where $A$ is the incidence matrix of a connected graph, and $b$ is a (non-proper) vertex $2$-colouring. In this context, Arkhipov's theorem states that the corresponding graph-LinBCS game has a perfect quantum strategy, and no perfect classical strategy, if and only if the graph is non-planar and the $2$-colouring $b$ has odd parity. In addition to efficient methods for detecting quantum and classical strategies for these games, we show that computing the classical value, a problem that is NP-hard for general LinBCS games can be done efficiently. In this work, we describe a graph-LinBCS game by a $2$-coloured graph and call the corresponding solution group a graph incidence group. As a consequence of the Robertson-Seymour theorem, we show that every quotient-closed property of a graph incidence group can be expressed by a finite set of forbidden graph minors. Using this result, we recover one direction of Arkhipov's theorem and derive the forbidden graph minors for the graph incidence group properties: finiteness, and abelianness. Lastly, using the representation theory of the graph incidence group, we discuss how our graph minor criteria can be used to deduce information about the perfect strategies for graph-LinBCS games.

Degree

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Paddock, Connor
Advisor dc:contributor.advisor
  • Yard, Jon

Subjects

dc:subject × 8

Rights

Language dc:language.iso
en

Identifiers

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

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

Paddock, Connor. Algebraic and combinatorial aspects of incidence groups and linear system non-local games arising from graphs. University of Waterloo, 2019. http://hdl.handle.net/10012/14744