4 ms·

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

by 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.

thaumasiotes 4y ago
> that instance is too hard, so we make it easier by forcing a color in the center (this is a form of symmetry breaking) The example of symmetry breaking in your post is "the instance of the largest color that appears closest to the center must appear in octant II". I can understand this - by using a combination of rotations and reflections, any coloring that doesn't satisfy this constraint can be transformed into one that does. So the patterns we reject by using this "symmetry-breaking" approach are those that are identical, through one or more symmetries, to a pattern we won't reject. So far so good. But forcing a color in the center can't be symmetry-breaking in this sense. Every symmetry of the diamond will map the center onto itself, so applying a "symmetry-breaking" rule that the center must be painted a particular color will let you rule out a total of zero patterns that can be transformed into patterns that match your rule. That is, literally, worthless. Such a constraint will let you rule out patterns that aren't transformable into the patterns you do consider... but that's bad, not good. What do you mean when you say that forcing a color in the center is a form of symmetry breaking?
- 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. :-/

by bsubs 4y ago

thaumasiotes 4y ago

> that instance is too hard, so we make it easier by forcing a color in the center (this is a form of symmetry breaking) The example of symmetry breaking in your post is "the instance of the largest color that appears closest to the center must appear in octant II". I can understand this - by using a combination of rotations and reflections, any coloring that doesn't satisfy this constraint can be transformed into one that does. So the patterns we reject by using this "symmetry-breaking" approach are those that are identical, through one or more symmetries, to a pattern we won't reject. So far so good. But forcing a color in the center can't be symmetry-breaking in this sense. Every symmetry of the diamond will map the center onto itself, so applying a "symmetry-breaking" rule that the center must be painted a particular color will let you rule out a total of zero patterns that can be transformed into patterns that match your rule. That is, literally, worthless. Such a constraint will let you rule out patterns that aren't transformable into the patterns you do consider... but that's bad, not good. What do you mean when you say that forcing a color in the center is a form of symmetry breaking?

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