3 ms·

Assume you know that 13 colors aren't enough and you want to prove that 14 aren't enough either. Any 14 packing-coloring of the grid must use color 6 somewhere,

by bsubs 4y ago

Assume you know that 13 colors aren't enough and you want to prove that 14 aren't enough either. Any 14 packing-coloring of the grid must use color 6 somewhere, as otherwise it would be only using 13 colors that are no better than colors {1, ..., 13}, and thus not enough. Now, you can imagine the diamond you're considering is centered around one of these 6s. This is breaking a different kind of symmetry; a translational one, as it's breaking the original symmetry of centering your diamond on any possible color, by choosing an arbitrary one. Granted, this is different form of symmetry-breaking as it's not about auto-morphisms on the set of solution. Also, it's totally possible that "symmetry breaking" was a bad choice of words; as long as you agree that it's a helpful idea as it significantly reduces the search space, we are on the same page. formalizing this might be tricky, I mean something like a bijection from (the set of mappings from an infinite packing-coloring to a fixed colored sub-graph) to itself.

thaumasiotes 4y ago
> Any 14 packing-coloring of the grid must use color 6 somewhere, as otherwise it would be only using 13 colors that are no better than colors {1, ..., 13}, and thus not enough. Now, you can imagine the diamond you're considering is centered around one of these 6s. This is breaking a different kind of symmetry; a translational one This is a good point; I had been thinking of the problem differently. In this model, the diamond is viewed as just being a window onto the infinite grid, and we're not interested in whatever properties it might have considered as a finite graph. Thinking about it this way, the idea that the coloring in your article disproves is that "there is a 14-packing-coloring of the infinite grid which uses a chessboard pattern for color 1". But then, since (by your later result) there is no 14-packing-coloring of the infinite grid, it's not too surprising that there isn't such a coloring that also features a chessboard. What bothers me in this discussion of the chessboard conjecture is the switch: you say "at this point, we were conjecturing that using color 1 in the chessboard pattern that yields density 1/2 was optimal, meaning that you could packing-color a graph D_r with k colors (...) if, and only if, you could do it enforcing the chessboard pattern of 1's". And this seems plausible, and the illustration provided as a counterexample isn't actually a counterexample to this statement. You can packing-color the graph shown there with 14 colors, and you can do so while enforcing the chessboard pattern of 1s. In your explanation here, you're viewing D_r as a subgraph of the successfully-colored infinite grid, not as a finite graph in its own right. That handily explains why the chessboard pattern goes around the center of D_r instead of through it. The illustration in the post does then show that there's a problem. But to my eye, the problem is in the premise of a successfully 14-packing-colored infinite grid, not in the chessboard conjecture. In between stating the chessboard conjecture and providing the counterexample, you changed what the chessboard conjecture said -- there is no reference to the infinite grid in your statement of the chessboard conjecture, but the illustration of a "counterexample" is a counterexample to a statement about the infinite grid. It feels wrong. :-/
- bsubs 4y ago
  I see what you’re saying, but note that as mentioned above I did edit the post based on your feedback to be precise, stating that the conjecture we disproved was that regardless of the center color the chessboard of 1s could be assumed wlog in any finite diamond . (Also this is stated correctly in the paper, which at the end is the “source of truth”) I agree with you that just saying “D_r can be colored with k colors iff it can be done with a chessboard pattern of 1s” is a slightly different statement to which our counterexample is not a counterexample, but I think you got trapped into my initial omission in the blog post, which was a writing mistake rather a mathematical mistake. I don’t think there’s anything wrong here, but sorry for the original version of this post being sloppy in the writing. I agree again with what you were saying some messages ago about how versions of the conjecture that do not consider the center color can be more mathematically interesting. A proof that D_r can be colored with k colors iff it can be done with the chessboard pattern would definitely be super nice.

by bsubs 4y ago

thaumasiotes 4y ago

> Any 14 packing-coloring of the grid must use color 6 somewhere, as otherwise it would be only using 13 colors that are no better than colors {1, ..., 13}, and thus not enough. Now, you can imagine the diamond you're considering is centered around one of these 6s. This is breaking a different kind of symmetry; a translational one This is a good point; I had been thinking of the problem differently. In this model, the diamond is viewed as just being a window onto the infinite grid, and we're not interested in whatever properties it might have considered as a finite graph. Thinking about it this way, the idea that the coloring in your article disproves is that "there is a 14-packing-coloring of the infinite grid which uses a chessboard pattern for color 1". But then, since (by your later result) there is no 14-packing-coloring of the infinite grid, it's not too surprising that there isn't such a coloring that also features a chessboard. What bothers me in this discussion of the chessboard conjecture is the switch: you say "at this point, we were conjecturing that using color 1 in the chessboard pattern that yields density 1/2 was optimal, meaning that you could packing-color a graph D_r with k colors (...) if, and only if, you could do it enforcing the chessboard pattern of 1's". And this seems plausible, and the illustration provided as a counterexample isn't actually a counterexample to this statement. You can packing-color the graph shown there with 14 colors, and you can do so while enforcing the chessboard pattern of 1s. In your explanation here, you're viewing D_r as a subgraph of the successfully-colored infinite grid, not as a finite graph in its own right. That handily explains why the chessboard pattern goes around the center of D_r instead of through it. The illustration in the post does then show that there's a problem. But to my eye, the problem is in the premise of a successfully 14-packing-colored infinite grid, not in the chessboard conjecture. In between stating the chessboard conjecture and providing the counterexample, you changed what the chessboard conjecture said -- there is no reference to the infinite grid in your statement of the chessboard conjecture, but the illustration of a "counterexample" is a counterexample to a statement about the infinite grid. It feels wrong. :-/

bsubs 4y ago
I see what you’re saying, but note that as mentioned above I did edit the post based on your feedback to be precise, stating that the conjecture we disproved was that regardless of the center color the chessboard of 1s could be assumed wlog in any finite diamond . (Also this is stated correctly in the paper, which at the end is the “source of truth”) I agree with you that just saying “D_r can be colored with k colors iff it can be done with a chessboard pattern of 1s” is a slightly different statement to which our counterexample is not a counterexample, but I think you got trapped into my initial omission in the blog post, which was a writing mistake rather a mathematical mistake. I don’t think there’s anything wrong here, but sorry for the original version of this post being sloppy in the writing. I agree again with what you were saying some messages ago about how versions of the conjecture that do not consider the center color can be more mathematically interesting. A proof that D_r can be colored with k colors iff it can be done with the chessboard pattern would definitely be super nice.