5 ms·
It was the comment I replied to that introduced infinitely large maps - but regardless I wasn't trying to be as clever as you might be trying to assume (and of
by OJFord 4y ago
It was the comment I replied to that introduced infinitely large maps - but regardless I wasn't trying to be as clever as you might be trying to assume (and of course not finding it :)) - I would have said the same about 'really large' or indeed 'just a bit larger than the 4 or 5 regions I described initially'.
> there is a kind of "spooky action at a distance" that can happen. Local decisions about colours can lead to implications across the other side of the structure. Proving that your local decisions can always be made in a way that doesn't cause problems elsewhere is the problem.
This is the bit I can't grasp - I honestly appreciate the responses and attempts to explain it, but it just (mistakenly, I can accept even if I don't understand) seems counter-intuitive to me. As in, intuitive that it extends, or that there's no such problem.
Maybe I just need to play with it on paper a bit, stumble into such a spooky action to get it.
> Now, exactly how do you extend that to a map with billions of regions?
I don't have the background for the precision you'd like I'm afraid (if I did, I'm sure I'd understand anyway!) but loosely - divide and conquer; a similar thing happens at the interface of all the 'sub-maps'?
- ColinWright 4y ago>> there is a kind of "spooky action at a distance" that can happen > This is the bit I can't grasp OK. Let me give you a collection of statements, each of which I can expand on, but which might give you a sense of the problem. * Instead of colouring regions in a map we can colour vertices of a graph; (put a vertex in each region and connect vertices if their regions share a border) * If a graph can be three-coloured then it can be four-coloured; (Any three colouring is a four colouring, but with no vertices of the fourth colour) * An instance of colouring an arbitrary graph can be converted into an instance of colouring a planar graph; (There is a "widget" that uncrosses edges) * Given a number to factor, we can construct a graph such that three-colouring the graph will produce a factorisation[0]; (Graph three-colouring is NP-Complete, so this is even easier than that) Broadly, we can construct a graph that has exactly one (up to permutation of colours) valid three-colouring. As you start to colour it you find that you have to make choices, on average about $4/3$ choices per vertex[1]. But the wrong choice results in not being able to complete the colouring, and you don't know which choice or choices were wrong. So you get this "spooky action at a distance" thing going on. Sometimes a planar graph can't be coloured with three colours, and sometimes it can but a colouring is hard to find. When we allow the extra colour it turns out that it's always possible, but it's not obvious that that should be the case. That's an #ISS-level view of the ideas ... hope it helps. [0] https://www.solipsys.co.uk/new/FactoringViaGraphThreeColouring.html?vl21hn https://www.solipsys.co.uk/new/FactoringViaGraphThreeColouri... [1] Beigel, R.; Eppstein, D. (2005), "3-coloring in time O(1.3289^n)"[2] [2] https://en.wikipedia.org/wiki/Graph_coloring#cite_note-15 https://en.wikipedia.org/wiki/Graph_coloring#cite_note-15 PS: I've upvoted you because I'm sure other people have the same questions, they're good questions, and they deserve answers.
- OJFord 4y agoI'm sure I'm mistaken, but I believe the conversion to a graph loses exactly the information I'm trying to use: a vertex with three edges, where each of those vertices are also all interconnected, can have a fourth edge to a fifth vertex which also has an edge to each of the others; on the map this is not possible. Right? From my napkin sketch to satisfy myself, I think you can show the same thing equivalently by saying 'and the edges are not allowed to cross' - but I don't know if that's something that exists in graph theory? (If so, it seems to me it should be used here? And if it is, well, finally we have a modicum of precision for what I'm trying to get at!) Edit: OK, sorry, that is a 'planar graph'.
- ColinWright 4y agoSo, to try to answer your questions: If you have a map in which you want to colour the regions, you can convert to a graph by putting a capital city in each region, then putting a road between two capitals of countries that share a border. Colouring the capital cities vertices) so that any joined by roads (edges) get different colours is exactly the same problem. The graph-colouring problem is more general now, but every planar graph is equivalent to a map and vice-versa ... there is a one-to-one correspondence between these problems. Now we move to the NP-Completeness of the 3-colouring of general graphs. That shows that this sort of thing is hard for the reasons I gave in the grandparent post. "But" I hear you say "That's for general graphs, and not for planar graphs!" Yes, but there is a way to convert a graph-colouring problem on a non-planar graph into an equivalent graph-colouring problem on a planar graph, so we neither gain nor lose much by consider just planar graphs. So 3-colouring planar graphs is NP-Complete. Then you get into my comments about making bad choices and having to backtrack, and spooky action at a distance. Hope that helps.