7 ms·

Let me be a bit more precise here (at risk of being pedantic) to make sure we're on the same page. (Also, if you have a concrete idea of how to reformulate the

• thaumasiotes 4y ago
  > Conjecture 1. A packing-coloring of the infinite square grid exists using colors {1, ..., k} if, and only if, there exists one with a chessboard pattern (meaning that wlog all vertices (a, b) such that a+b is odd get color 1). I understand this, but I'll need to refer to it in a moment... > Conjecture 2. Let $D_{r, k, c}$ be the instance consisting of whether $D_r$ can be packing-colored with $k$ colors assuming it gets color $c$ in the center. Then enforcing that all vertices (a, b) such a+b is odd get color 1 does not change the satisfiability of the instance. I'll assume that D_r refers to a taxicab disc ("diamond") of radius r? Conjecture 2 is well-defined, but I see several problems with it. Conjecture 1 seems like a reasonable thing to investigate (though it's not what I had in mind); Conjecture 2 doesn't. Most obviously, Conjecture 2 is false, since D_{r, k, 1} is dramatically affected by forcing all cells at an odd taxicab distance from the center to take color 1. Second, while you are correct to say that the existence of any checkerboard pattern which successfully k-colors the infinite grid implies the existence of a checkerboard pattern which k-colors the infinite grid and assigns color 1 to those vertices (a, b) such that a+b is odd, the same cannot be said (and you haven't said it) about a finite grid. It it then not obvious why, when discussing a finite grid, you want to restrict checkerboard patterns to those which assign color 1 to vertices at an odd taxicab distance from the center of the grid. You can't say "without loss of generality" about that choice; the grid is no longer infinite. In your 14-diamond, this presents the problem that the off-center checkerboard cannot color half of the cells in the grid, because -- to use a chessboard analogy -- the number of "black" cells is not equal to the number of "white" cells. This suggests an obvious reason why a checkerboard that is forced to color the smaller half of the diamond might prove to be inadequate to the task. Third, it is not obvious why you want to restrict yourself to grids that have a center cell. The following grid is not a taxicab disc: xxxxxx xxxxxx xxxxxx xxxxxx xxxxxx xxxxxx But it can be colored and it can be given a checkerboard pattern. And unlike a diamond, it can be used to tile the infinite grid with its checkerboard pattern intact. The question I'm really asking here is, I guess, "What is the point of your Conjecture 2? Who would care what the answer was?" You introduced it as a way to cut down on the search space for a computationally-intensive trial-and-error problem, and it appears to be effective at that goal. But you go on to say that you can't use it to achieve that goal because it's false, when a version of your conjecture that is (1) much more natural to pose; and (2) equally useful for the purpose of cutting the search space, might still be true! You wouldn't want the checkerboard to avoid the center of a diamond anyway, because if it goes through the center of the diamond, it will give you a bigger reduction in the search space than the checkerboard that avoids the center will! Why is the conjecture not this one? Checkerboard Conjecture: for any "interesting subset" [Diamonds on the grid? Bounded convex subsets of the grid? Connected subsets? This can be refined; maybe diamonds are fine.] of the infinite grid ℤ², if any packing-coloring exists with k colors, then a packing-coloring exists with k colors in which color 1 forms a checkerboard. That is to say, any two vertices v = (a, b) and w = (c, d) satisfy a+b ≡ c+d (mod 2) if and only if (either v and w both have color 1, or v and w both fail to have color 1).
  • bsubs 4y ago
    I think I see what you mean, but it seems to me that you're mixing ideas about the chessboard conjecture in this particular context, with more general versions of the conjecture (a bunch of which we don't know the answer for, and might be interesting in their own right). In particular, to show that the packing-chromatic number of the infinite grid is 15, we needed to find a finite subgraph of the infinite square grid for which 14 colors are not enough. The class of sub-graphs that seemed more amenable to do this was that of diamonds (i.e., disks in the corresponding metric) of radius r. If you simply try to determine whether D_{14} can be packing-colored with 14 colors, that instance is too hard, so we make it easier by forcing a color in the center (this is a form of symmetry breaking). Forcing the center to take color 1 is the worst possible choice (see Fig 6. of the paper https://arxiv.org/pdf/2301.09757v1.pdf https://arxiv.org/pdf/2301.09757v1.pdf), therefore we want to force it to something other than 1, let's say 6 (this seems to be the best choice in practice). Your problem then reduces to determine whether D_{14} can be packing-colored with 14 colors, when forcing a 6 in the center. It turns out again that this is not easy enough to solve naively, so it would be really nice it we could assume without loss of generality that we can enforce the chessboard pattern as well as the 6 in the center (which given that the center has even coordinates, it would imply that the 1s are at odd coordinates). I try to prove this manually and failed. But we ran the experiment assuming the conjecture to be true, and effectively there is no packing-coloring for D_{14} with 14 colors, a 6 in the center, and 1s in every odd coordinate. If Conjecture 2 had been true, then we would have ended our work there, but then we realize we couldn't assume Conjecture 2: we found a way of packing-coloring D_{14} with a 6 in the center when removing the chessboard assumption. So the formalization in our context that made the most sense was: "is it true that given any radius r, any value of k, and any value of c, the forced center color, we can assume the chessboard pattern?" (Noting that if the center is forced to 1 as you mention in your comment, then the chessboard pattern would be 1s on the even coordinates). This is what I meant with Conjecture 2, so hopefully now it's clear why it was of interest for this particular problem. It's not obvious at all that Conjecture 2 is false provided this! unless you have a new argument I'm unaware of! Your last question is of course interesting, and many variations of the conjecture make sense and could be studied; we didn't really pose Conjecture 2 thinking it was the most interesting formulation, but rather a sufficiently simple one that would have justified our result of (D_{14}+6 in the center + 1s at odd coordinates)-is-not-packing-colorable-with-14-colors to imply the final result.