Comment

Comment by bsubs

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

parent bsubs 3 years ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton