论文标题
Arkhipov的定理，图形未成年人和线性系统非本地游戏
Arkhipov's theorem, graph minors, and linear system nonlocal games
论文作者
论文摘要
线性系统游戏的完美量子策略对应于其解决方案组的某些表示。我们研究图形入击游戏的解决方案组，它们是线性系统游戏，其中底层线性系统是（非授权）两色图的发射系统。虽然不可证实的是确定通用线性系统游戏是否具有完美的量子策略，但对于图形发射游戏，Arkhipov的定理解决了该问题，该问题指出，当它具有完美的经典策略或图形不是Planplanar的情况下，它只有当它具有完美的时，它的图形发射率游戏具有完美的量子策略。 Arkhipov的标准可以在连接的两色图上作为禁止的次要条件。我们通过表明，对于连接的两色图的图形发射游戏，我们扩展了Arkhipov的定理，解决方案组的每个商封闭属性都具有禁止的次要表征。我们从小组理论的角度重新播放了Arkhipov的定理，然后找到禁忌的未成年人的两个新属性：有限和阿贝利亚。我们的方法完全是组合的，找到其他商品封闭特性的禁止的未成年人似乎是一个有趣的组合问题。
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.
