Arkhipov's theorem, graph minors, and linear system nonlocal games

• URL: http://arxiv.org/abs/2205.04645v2
• Date: Mon, 18 Jul 2022 18:40:15 GMT
• Title: Arkhipov's theorem, graph minors, and linear system nonlocal games
• Authors: Connor Paddock, Vincent Russo, Turner Silverthorne, and William Slofstra
• Abstract summary: We study the solution groups of graph incidence games in which the underlying linear system is the incidence system of a two-coloured graph. Arkhipov's theorem 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. 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• A Systematization of the Wagner Framework: Graph Theory Conjectures and Reinforcement Learning [0.3111424566471946]
  Adam Zsolt Wagner proposed an approach to disprove conjectures in graph theory using Reinforcement Learning (RL) We present four distinct single-player graph-building games employing various RL algorithms. We also propose a principled approach to select the most suitable neural network architecture for any given conjecture.
  arXiv  Detail & Related papers  (2024-06-18T14:40:20Z)
• Communication Complexity of Graph Isomorphism, Coloring, and Distance Games [0.0]
  We show that perfect non-signalling strategies collapse communication complexity under favorable conditions. Surprisingly, we observe that non-signalling strategies provide a finer distinction for the new game compared to classical and quantum strategies.
  arXiv  Detail & Related papers  (2024-06-04T10:53:16Z)
• Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
  We present a novel end-to-end contrastive graph clustering model named CONGREGATE. To support geometric clustering, we construct a theoretically grounded Heterogeneous Curvature Space. We then train the graph clusters by an augmentation-free reweighted contrastive approach.
  arXiv  Detail & Related papers  (2023-05-05T14:04:52Z)
• Learning Universe Model for Partial Matching Networks over Multiple Graphs [78.85255014094223]
  We develop a universe matching scheme for partial matching of two or multiple graphs. The subtle logic for inlier matching and outlier detection can be clearly modeled. This is the first deep learning network that can cope with two-graph matching, multiple-graph matching, online matching, and mixture graph matching simultaneously.
  arXiv  Detail & Related papers  (2022-10-19T08:34:00Z)
• On the relation between completely bounded and $(1,cb)$-summing maps with applications to quantum XOR games [65.51757376525798]
  We show that given a linear map from a general operator space into the dual of a C$*$-algebra, its completely bounded norm is upper bounded by a universal constant times its $(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  arXiv  Detail & Related papers  (2021-12-09T21:06:52Z)
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  We tackle the problem of exactly recovering an unknown ground-truth binary labeling of the nodes from a single corrupted observation of each edge. We apply a hierarchy of relaxations known as the sum-of-squares hierarchy, to the problem. We show that the solution of the dual of the relaxed problem is related to finding edge weights of the Johnson and Kneser graphs.
  arXiv  Detail & Related papers  (2021-02-16T08:36:19Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• The quantum-to-classical graph homomorphism game [0.0]
  We introduce a graph homomorphism game between quantum graphs and classical graphs. We show that winning strategies in the various quantum models for the game is an analogue of the notion of non-commutative graph homomorphisms. We also demonstrate explicit quantum colorings of all quantum complete graphs, yielding the surprising fact that the algebra of the $4$-coloring game for a quantum graph is always non-trivial.
  arXiv  Detail & Related papers  (2020-09-15T17:09:35Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  We identify conditions which allow one to lift one dimensional solutions to solutions on graphs. We show that even for a simple example of a topologically interesting graph the corresponding non-trivial Lax pairs and associated unitary transformations do not lift to a Lax pair on the Z-graded graph.
  arXiv  Detail & Related papers  (2020-08-11T17:58:13Z)
• Synchronous linear constraint system games [0.0]
  We show that the game algebra is a suitable quotient of the group algebra of the solution group. We also demonstrate that linear constraint system games are equivalent to graph isomorphism games on a pair of graphs parameterized by the linear system.
  arXiv  Detail & Related papers  (2020-07-06T14:31:59Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.