Please call this the Peter Wilson Proof dated 5/10/18 at 7 in the morning AE standard time & I hope no one else has done it yet!

Here goes;

Draw two circles around one of the points at the center such that they could cross the outer edges of the dots and assume all the dots are filled in.

At the outer two edge rows of dots, the 2nd most outer being say red and blue alternating, and the outer one being green and yellow alternating then this can go on layer by layer indefinitely.

The circle diameters approach each other but can never meet.

Until (and if) there needs to be an odd number of dots in the outer circle layer. Then there are two colours the same next to each other, hence the need for 5 colours. Ok this matches the earlier proof.

Now this fifth colour can be used on the two outer layers of dots if both contain coincidentally odd numbers of dots.

What happens when the fifth colour is adjacent in the two outer layers? You just rotate the layers slightly and the colours don’t coincide. Now it doesn’t matter if the two outer layers of dots are odd or even in total which is ALWAYS the case. The fifth colour can ALWAYS be offset and only needs to be used at most once in a layer of dots.

Ok so now overlay another set of dots. if one or two don’t coincide then none ever will be exactly 1 unit away from the first set. If two coincide then it is the same set. If only one coincides then exactly no others can ever coincide. Either way the original solution stands.

]]>> But yeah, that totally does it. I didnâ€™t know at all about that bound on the purely existential theory though! Interesting, thanksâ€¦

Did this not come up in the infamous conversation I had with you when Ettienne and I got back that one time at PROMYS, or did we only discuss the complexity of the general decidability of questions involving the reals?

]]>Let me just expand on Josh Zelinsky’s point here and point out that in fact much more is true. We can define the *girth* of a graph to be the size of the smallest cycle (if there are no cycles, the girth is ∞.)

Obviously, a graph with girth ∞ is necessarily 2-colorable. But for finite girth, for graphs that do indeed contain a cycle, Erdos showed that you can find graphs with arbitrarily high girth and arbitrarily high chromatic number.

…except that actually, that’s only true if when we say “arbitrarily high chromatic number”, we’re only talking about *finite* possibilities for the chromatic number! I was implicitly restricting to finite graphs above. But if we want to allow infinite graphs, and if we thus similarly allow the chromatic number to be infinite, this is no longer true: It’s a theorem of Erdos and Hajnal that any graph with no 4-cycles is countably colorable!

(OK, the theorem is actually much stronger than that — what it actually says is, if a graph is not countably colorable, then it contains, for every n, a copy of the complete bipartite graph K_{n,aleph_1}. But in particular that means it contains a 4-cycle. ðŸ™‚ )

However, with a modification, the theorem becomes true for infinite chromatic numbers as well. We can define the *odd girth* of a graph to be the size of the smallest *odd* cycle (so the odd girth is ∞ if and only if the graph is 2-colorable). Restricting ourselves once again to graphs of finite odd girth, graphs that do indeed contain an odd cycle, it is indeed the case (and yes this is Erdos again ðŸ˜› ) that you can find graphs of arbitrarily high odd girth and arbitrarily high chromatic number — even if the chromatic number is allowed to be an infinite cardinal.

In particular, there are triangle-free graphs with arbitrarily high chromatic number, even if the chromatic number is allowed to be an infinite cardinal. ðŸ™‚

(The construction for this last theorem isn’t too bad, either! IIRC it goes as follows: Say you want a graph with chromatic number at least X and odd girth at least 1+2n. Take Y=℘^n(X) (i.e., take the power set of X, iterated n times), and put a total order on it (obviously using choice there, but interestingly not its full strength; it doesn’t need to be a well-order). Turn Y into a directed graph by drawing an edge from a to b if a<b. Now, given a directed graph G, we’ll define its directed line graph, L(G), to be the graph whose vertices are the edges of G, and for edges e and e’ of G, we’ll draw an edge from e to e’ in L(G) if the head of e equals the tail of e’. We’ll take L^n(G). Then the underlying undirected graph of this has the required chromatic number and odd girth!)

]]>