The Packing Chromatic Number of the Infinite Square Grid is 15

• URL: http://arxiv.org/abs/2301.09757v1
• Date: Mon, 23 Jan 2023 23:27:41 GMT
• Title: The Packing Chromatic Number of the Infinite Square Grid is 15
• Authors: Bernardo Subercaseaux and Marijn J. H. Heule
• Abstract summary: 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.
• Score: 5.863264019032882
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A packing $k$-coloring is a natural variation on the standard notion of graph $k$-coloring, where vertices are assigned numbers from $\{1, \ldots, k\}$, and any two vertices assigned a common color $c \in \{1, \ldots, k\}$ need to be at a distance greater than $c$ (as opposed to $1$, in standard graph colorings). Despite a sequence of incremental work, determining the packing chromatic number of the infinite square grid has remained an open problem since its introduction in 2002. We culminate the search by proving this number to be 15. We achieve this result by improving the best-known method for this problem by roughly two orders of magnitude. The most important technique to boost performance is a novel, surprisingly effective propositional encoding for packing colorings. Additionally, we developed an alternative symmetry-breaking method. Since both new techniques are more complex than existing techniques for this problem, a verified approach is required to trust them. We include both techniques in a proof of unsatisfiability, reducing the trusted core to the correctness of the direct encoding.

Related papers

• 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)
• Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods [18.47705532817026]
  We study the problem of finding an $epsilon$firstorder stationary point (FOSP) of a smooth function.<n>We introduce a novel optimistic quasi- gradient approximation method to solve this online learning problem.
  arXiv  Detail & Related papers  (2024-12-03T05:20:05Z)
• A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
  We construct an algorithm that returns a point $hat xin barmathcal X$ such that $f(hat x)$ is as small as possible. We prove that this method is such that the $f(hat x) - min_xin barmathcal X f(x)$ is of smaller order than $d2/sqrtn$ up to poly-logarithmic terms.
  arXiv  Detail & Related papers  (2024-06-26T18:19:10Z)
• Edge coloring lattice graphs [0.0]
  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.
  arXiv  Detail & Related papers  (2024-02-13T19:38:58Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
  We give a statistical characterization of the $gamma$-regret for arbitrary structured bandit problems. The $gamma$-regret emerges in structured bandit problems over a function class $mathcalF$ where finding an exact optimum of $f in mathcalF$ is intractable.
  arXiv  Detail & Related papers  (2023-03-06T17:54:33Z)
• Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods [57.050204432302195]
  This work proposes a universal and adaptive second-order method for minimizing second-order smooth, convex functions. Our algorithm achieves $O(sigma / sqrtT)$ convergence when the oracle feedback is with variance $sigma2$, and improves its convergence to $O( 1 / T3)$ with deterministic oracles.
  arXiv  Detail & Related papers  (2022-11-03T14:12:51Z)
• 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)
• Evolutionary Algorithm for Graph Coloring Problem [0.0]
  The graph coloring problem (GCP) is one of the most studied NP-HARD problems in computer science. In our paper, we start with the theoretical upper bound of chromatic number, that is, maximum out-degree + 1. In the process of evolution some of the colors are made unused to dynamically reduce the number of color in every generation.
  arXiv  Detail & Related papers  (2021-11-17T12:16:57Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  This paper presents a convex-analytic framework to learn from data. We show that a triangular convexity decomposition is guaranteed by a transform of the corresponding to its upper part.
  arXiv  Detail & Related papers  (2021-09-17T17:46:12Z)
• A deep learning guided memetic framework for graph coloring problems [15.426481600285724]
  We present a new framework which combines a deep neural network with the best tools of "classical" metaheuristics for graph coloring. A study of the contribution of deep learning in the algorithm highlights that it is possible to learn relevant patterns useful to obtain better solutions to this problem.
  arXiv  Detail & Related papers  (2021-09-13T13:17:41Z)
• 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)
• Simple vertex coloring algorithms [2.8808678188754637]
  We give a simple algorithm for $(1 + epsilon)Delta$-coloring. It can be adapted to a quantum query algorithm making $tildeO(epsilon-1n4/3)$ queries.
  arXiv  Detail & Related papers  (2021-02-14T07:27:10Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  In this paper, we denote the non-strongly setting on the magnitude of a gradient-free minimax optimization problem. We show that a novel zeroth-order variance reduced descent algorithm achieves the best known query complexity.
  arXiv  Detail & Related papers  (2020-06-16T17:55:46Z)
• GeoDA: a geometric framework for black-box adversarial attacks [79.52980486689287]
  We propose a framework to generate adversarial examples in one of the most challenging black-box settings. Our framework is based on the observation that the decision boundary of deep networks usually has a small mean curvature in the vicinity of data samples.
  arXiv  Detail & Related papers  (2020-03-13T20:03:01Z)

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.