4 ms·

Thanks! this is a correct answer. Indeed I stated the conjecture a bit imprecisely in the blog post (the paper is more detailed in this respect). Just to make

• thaumasiotes 4y ago
  > In simpler words, the conjecture was that you could assume without loss of generality that the 1s would make a chessboard pattern, and this is not true in general. It is however likely that a modified version of the chessboard conjecture is true. In particular I'm interested in the conjecture that was stated in the post. That one just says "if a k-coloring exists, then a k-coloring in which the 1s form a perfect checkerboard pattern also exists". That seems like it's enough to allow you to assume without loss of generality that the 1s form a checkerboard pattern. That's still a huge reduction in the search space - you need to consider that the pattern might be shifted, but that only doubles the amount of work you're doing (since there are only two ways to fill in a checkerboard pattern on a grid), while filling in the checkerboard cuts the amount of work you're doing by a factor of 2^k. Also, it seems like something of an "error" (maybe not! What do we know about aperiodic colorings?) when thinking about checkerboarding to spend time considering graphs that won't tile the plane. The radius-14 diamond can't tile the plane while checkerboarded; a checkerboard pattern will hit more or less than half of the cells in the grid.
  • bsubs 4y ago
    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 text so this is clearer, I'm definitely interested!) Here are two well-defined conjectures: 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). 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. Conjecture 1 is true, based on our paper: if k <= 14, then no packing-coloring exists anyway, so the conjecture is vacuously true. If k >= 15, then we know of a packing-coloring that respects the chessboard pattern (the one in Figure 12), and so the conjecture holds. Conjecture 2 is false, this is where the smallest counterexample in the post kicks in. Note that given that 13 colors are not enough, we knew that if there was a solution with 14 colors, it must use color 6 somewhere, and by restricting ourselves to $D_{14}$ around such a vertex, we run into the issue! About your last comment, we use diamond graphs to prove lower bounds (i.e., that a certain number of colors is not enough), while finite square grids are used to prove upper bounds (as in Figure 12). About aperiodic colorings, see the other comment in this thread were we discuss about it a bit :)
    • 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).