> 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).
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:
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).