Voir la notice de l'article provenant de la source Numdam
The perfect quantum strategies of a linear system game correspond to certain representations of its solution group. We study the solution groups of graph incidence games, which are linear system games in which the underlying linear system is the incidence system of a (non-properly) two-coloured graph. While it is undecidable to determine whether a general linear system game has a perfect quantum strategy, for graph incidence games this problem is solved by Arkhipov’s theorem, which states that the graph incidence game of a connected graph has a perfect quantum strategy if and only if it either has a perfect classical strategy, or the graph is nonplanar. Arkhipov’s criterion can be rephrased as a forbidden minor condition on connected two-coloured graphs. We extend Arkhipov’s theorem by showing that, for graph incidence games of connected two-coloured graphs, every quotient closed property of the solution group has a forbidden minor characterization. We rederive Arkhipov’s theorem from the group theoretic point of view, and then find the forbidden minors for two new properties: finiteness and abelianness. Our methods are entirely combinatorial, and finding the forbidden minors for other quotient closed properties seems to be an interesting combinatorial problem.
Paddock, Connor 1 ; Russo, Vincent 2 ; Silverthorne, Turner 3 ; Slofstra, William 4
CC-BY 4.0
@article{ALCO_2023__6_4_1119_0,
author = {Paddock, Connor and Russo, Vincent and Silverthorne, Turner and Slofstra, William},
title = {Arkhipov{\textquoteright}s theorem, graph minors, and linear system nonlocal games},
journal = {Algebraic Combinatorics},
pages = {1119--1162},
publisher = {The Combinatorics Consortium},
volume = {6},
number = {4},
year = {2023},
doi = {10.5802/alco.292},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.5802/alco.292/}
}
TY - JOUR AU - Paddock, Connor AU - Russo, Vincent AU - Silverthorne, Turner AU - Slofstra, William TI - Arkhipov’s theorem, graph minors, and linear system nonlocal games JO - Algebraic Combinatorics PY - 2023 SP - 1119 EP - 1162 VL - 6 IS - 4 PB - The Combinatorics Consortium UR - http://geodesic.mathdoc.fr/articles/10.5802/alco.292/ DO - 10.5802/alco.292 LA - en ID - ALCO_2023__6_4_1119_0 ER -
%0 Journal Article %A Paddock, Connor %A Russo, Vincent %A Silverthorne, Turner %A Slofstra, William %T Arkhipov’s theorem, graph minors, and linear system nonlocal games %J Algebraic Combinatorics %D 2023 %P 1119-1162 %V 6 %N 4 %I The Combinatorics Consortium %U http://geodesic.mathdoc.fr/articles/10.5802/alco.292/ %R 10.5802/alco.292 %G en %F ALCO_2023__6_4_1119_0
Paddock, Connor; Russo, Vincent; Silverthorne, Turner; Slofstra, William. Arkhipov’s theorem, graph minors, and linear system nonlocal games. Algebraic Combinatorics, Tome 6 (2023) no. 4, pp. 1119-1162. doi: 10.5802/alco.292
Cité par Sources :