Edge coloring lattice graphs

• URL: http://arxiv.org/abs/2402.08752v1
• Date: Tue, 13 Feb 2024 19:38:58 GMT
• Title: Edge coloring lattice graphs
• Authors: Joris Kattem\"olle
• Abstract summary: We prove a necessary and sufficient condition for a proper edge coloring of a patch of a lattice graph by translation. This condition forms the cornerstone of a method that finds nearly minimal or minimal edge colorings of infinite lattice graphs. Our work finds direct application by offering minimal-depth quantum circuits in the areas of quantum simulation, quantum optimization, and quantum state verification.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop the theory of the edge coloring of infinite lattice graphs, proving a necessary and sufficient condition for a proper edge coloring of a patch of a lattice graph to induce a proper edge coloring of the entire lattice graph by translation. This condition forms the cornerstone of a method that finds nearly minimal or minimal edge colorings of infinite lattice graphs. In case a nearly minimal edge coloring is requested, the running time is $O(\mu^2 D^4)$, where $\mu$ is the number of edges in one cell (or `basis graph') of the lattice graph and $D$ is the maximum distance between two cells so that there is an edge from within one cell to the other. In case a minimal edge coloring is requested, we lack an upper bound on the running time, which we find need not pose a limitation in practice; we use the method to minimal edge color the meshes of all $k$-uniform tilings of the plane for $k\leq 6$, while utilizing modest computational resources. We find that all these lattice graphs are Vizing class~I. Relating edge colorings to quantum circuits, our work finds direct application by offering minimal-depth quantum circuits in the areas of quantum simulation, quantum optimization, and quantum state verification.

Related papers

• Minimizing the number of edges in LC-equivalent graph states [0.0]
  Local Clifford operations that map one graph state to another can alter the structure of the corresponding graphs, including changing the number of edges.<n>Here, we tackle the associated edge-minimization problem: finding graphs with the minimum number of edges in the LC-equivalence class of a given graph.
  arXiv  Detail & Related papers  (2025-05-30T22:49:45Z)
• Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges [8.499685241219366]
  We consider a framework for clustering edge-colored hypergraphs, where the goal is to cluster objects based on the primary type of multiway interactions they participate in. One well-studied objective is to color nodes to minimize the number of unsatisfied hyperedges. We provide new algorithms for maximizing satisfied edges, which is the same at optimality but is much more challenging to approximate.
  arXiv  Detail & Related papers  (2025-02-18T16:20:50Z)
• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  We provide a unified analysis of two-timescale gradient ascent (TTGDA) for solving structured non minimax optimization problems. Our contribution is to design TTGDA algorithms are effective beyond the setting.
  arXiv  Detail & Related papers  (2024-08-21T20:14:54Z)
• The Power of Graph Sparsification in the Continual Release Model [48.65946341463292]
  We make novel use of assorted sparsification techniques from the non-private streaming and static graph algorithms. Our edge-differentially private algorithms use sublinear space with respect to the number of edges in the graph. We conclude with additive error lower bounds for edge-privacy in the fully dynamic setting.
  arXiv  Detail & Related papers  (2024-07-24T20:15:07Z)
• Local random quantum circuits form approximate designs on arbitrary architectures [0.1977825609388727]
  We consider random quantum circuits (RQC) on arbitrary connected graphs whose edges determine the allowed $2$-qudit interactions. We prove that RQCs on graphs with spanning trees of bounded degree and height form $k$-designs after $O(mathrmpoly(k))$ gates. We identify larger classes of graphs for which RQCs generate approximate designs in circuit size.
  arXiv  Detail & Related papers  (2023-10-30T08:48:14Z)
• Planted Bipartite Graph Detection [13.95780443241133]
  We consider the task of detecting a hidden bipartite subgraph in a given random graph. Under the null hypothesis, the graph is a realization of an ErdHosR'enyi random graph over $n$ with edge density $q$. Under the alternative, there exists a planted $k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$.
  arXiv  Detail & Related papers  (2023-02-07T18:18:17Z)
• The Packing Chromatic Number of the Infinite Square Grid is 15 [5.863264019032882]
  A packing $k$-coloring is a variation on the standard notion of graph $k$-coloring. We prove the packing number of the infinite square grid by improving the best-known method by roughly two orders of magnitude.
  arXiv  Detail & Related papers  (2023-01-23T23:27:41Z)
• Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis [69.08838724594584]
  Finding shortest paths in a graph is relevant for numerous problems in computer vision and graphics. We introduce the novel graph-theoretic concept of a shortest path in a graph with matrix-valued edges.
  arXiv  Detail & Related papers  (2021-12-08T08:23:37Z)
• Withdrawn: A Measurement-based Algorithm for Graph Colouring [0.5482532589225553]
  In a previous version of this document we misinterpreted the runtime of a part of the described algorithm. We present a novel algorithmic approach to find a proper colouring of a graph with $d$ colours, if it exists.
  arXiv  Detail & Related papers  (2021-11-29T09:17:34Z)
• Faster Perturbed Stochastic Gradient Methods for Finding Local Minima [92.99933928528797]
  We propose tttPullback, a faster perturbed gradient framework for finding local minima. We show that Pullback with gradient estimators such as SARAH/SP and STORM can find $(epsilon, epsilon_H)$approximate local minima within $tilde O(epsilon-3 + H-6)$. The core idea of our framework is a step-size pullback'' scheme to control the average movement of the gradient evaluations.
  arXiv  Detail & Related papers  (2021-10-25T07:20:05Z)
• Optimizing Ansatz Design in QAOA for Max-cut [0.9126120966154119]
  CNOT is one of the primary sources of error in modern quantum computers. In this paper, we propose two hardware independent methods to reduce the number of CNOT gates in the circuit.
  arXiv  Detail & Related papers  (2021-06-05T06:43:48Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  We prove that the practical single loop accelerated gradient tracking needs $O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$. Our convergence rates improve significantly over the ones of $O(frac1epsilon5/7)$ and $O(fracLmu)5/7frac1 (1-sigma)1.5logfrac1epsilon)$.
  arXiv  Detail & Related papers  (2021-04-06T15:34:14Z)
• Learning Graphons via Structured Gromov-Wasserstein Barycenters [143.42601038462965]
  We propose a novel and principled method to learn a nonparametric graph model called graphon. The proposed approach overcomes drawbacks of prior state-of-the-art methods, and outperforms them on both synthetic and real-world data.
  arXiv  Detail & Related papers  (2020-12-10T13:04:29Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)

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.