4 ms·

> Can the diamond of radius 14 be colored using a checkerboard pattern of 1s when the center color isn't 6? Yes - the counterexample given can be shifted left

> Can the diamond of radius 14 be colored using a checkerboard pattern of 1s when the center color isn't 6? Yes - the counterexample given can be shifted left by 1, making a the center color 1 (more 1s can be inserted completing the checkerboard pattern). I suspect that the conjecture to which this is a counterexample was imprecisely stated in the blog post, although there could also be a reason that a counterexample with a 6 in the center leads to a general counterexample.

bsubs 4y ago
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 it fully precise, the conjecture was that if you take any $D_r$ graph, and force any color in the center (to avoid parity considerations that shift the chessboard pattern, assume the center color is different from $1$), then you can packing-color it if and only if you can do so after enforcing the chessboard pattern. 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, Don Knuth thinks it holds for all diamonds of odd radius. There is a precise way of formalizing his variant of the conjecture. However, I'm not too inclined to work on it now that the core problem has been solved... About the "why 6 in the center?" implicit question in your comment: this is a nice question and I unfortunately only have a speculative answer (which is stated to some degree in the paper as we have an entire section on how to choose the center-color). In some sense, there's not really a way to answer this question super nicely: this is the smallest counter-example, and for some reason of the mathematical universe no smaller counter-example exists. I'm 90% sure that 6 is the smallest center-color for which a counter-example of this size exists. It's definitely possible to run 5 more experiments to confirm this, although given that it costs money to do so (even if neither me or my advisor are directly paying for the computing resources), I'm not sure if it's worth doing.
- 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 :)

bsubs 4y ago

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 it fully precise, the conjecture was that if you take any $D_r$ graph, and force any color in the center (to avoid parity considerations that shift the chessboard pattern, assume the center color is different from $1$), then you can packing-color it if and only if you can do so after enforcing the chessboard pattern. 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, Don Knuth thinks it holds for all diamonds of odd radius. There is a precise way of formalizing his variant of the conjecture. However, I'm not too inclined to work on it now that the core problem has been solved... About the "why 6 in the center?" implicit question in your comment: this is a nice question and I unfortunately only have a speculative answer (which is stated to some degree in the paper as we have an entire section on how to choose the center-color). In some sense, there's not really a way to answer this question super nicely: this is the smallest counter-example, and for some reason of the mathematical universe no smaller counter-example exists. I'm 90% sure that 6 is the smallest center-color for which a counter-example of this size exists. It's definitely possible to run 5 more experiments to confirm this, although given that it costs money to do so (even if neither me or my advisor are directly paying for the computing resources), I'm not sure if it's worth doing.

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