# Polymath16, sixth thread: Wrestling with infinite graphs

This is the sixth “research” thread of the Polymath16 project to make progress on the Hadwiger–Nelson problem, continuing this post. This project is a follow-up to Aubrey de Grey’s breakthrough result that the chromatic number of the plane is at least 5. Discussion of the project of a non-research nature should continue in the Polymath proposal page. We will summarize progress on the Polymath wiki page.

Here’s a brief summary of the progress made in the previous thread:

– The smallest known unit-distance graph of chromatic number 5 now has 610 vertices and 3000 edges.

– We now have several small unit-distance graphs with no 4-coloring in which a particular vertex is bi-chromatic, and these results are human-provable.

– We now have upper bounds on the chromatic number of $\mathbb{R}^d$ for $d=5,6$.

Progress has slowed considerably since the end of the spring semester (presumably due to summer travel, etc.). I wanted to highlight a couple of questions to help keep the conversation going:

Question. Is Tamas’s result that every 4-coloring of $\mathbb{Z}[\omega_1,\omega_3]$ is 8-periodic human-provable?

Terry Tao provided a comment along these lines. Actually, a human proof of $\textrm{CNP}\geq5$ can be obtained from something much weaker:

Question. Is it easy to check whether an infinite k-colorable graph has finitely many k-colorings?

Indeed, Boris has an easy proof of the following: If there exists a unit-distance graph with infinite Euclidean diameter and finitely many k-colorings, then the chromatic number of the plane is at least k+1. As such, a human proof of $\textrm{CNP}\geq5$ reduces to human-proving that $\mathbb{Z}[\omega_1,\omega_3]$ has finitely many 4-colorings.

Question. What sort of lower bounds can we get on CNP if we use a version of Lovasz that’s higher on the SOS hierarchy?

We know that the (complementary) Lovasz number of the plane is about 3.48. Applying this semidefinite program to Marijn’s graph on 874 vertices gives a lower bound of about 3.37. Can we beat 3.48 by running an SOS program on one of our 5-chromatic graphs? What if we applied ideas from Oliveira’s thesis to compute with the entire plane?

## 110 thoughts on “Polymath16, sixth thread: Wrestling with infinite graphs”

1. Philip Gibbs says:

We know a lot about 4-colourings of $R_2 = \mathbb{Z}[\omega_1,\omega_3]$ including the essentially complete description given by Tamas, but not much of it has yet been reduced to human proofs.

We know that for any four colouring $c_4$ the colour of the vertex at 8/3 is the same as the colour at the origin $c_4(8/3) = c_4(0)$ This can be shown to be equivalent to general periodicity of 8 i.e. $c_4(x) = c_4(x+8y)$ for all $x,y \in R_2$. This is also true in any ring that is an extension of $R_2$ by additional elements of unit modulus. The only reason that the special case for 8/3 has prominence is that $8/3 = \omega_3 + \overline{\omega}_3 + 1$ so this vertex appears in small graphs with just three sums of unit vectors.

For another example we can compute $\omega_3^3 - 1 = \eta^6 - 1 = 8 \times \frac{-4+11i\sqrt{11}}{27}$ Therefore $c_4(x) = c_4(x+(\eta^6-1)y)$ and in particular $c_4(x) = c_4(\eta^6 x)$ which is the rotational symmetry observed by Tamas.

Another thing we know about four colourings in $R_2$ is that no hexagon has a monochromatic triangle. This was shown by Audrey using the graph $M$ which can be reduced to a graph $M_1$ with only 278 vertices. I have not followed all the comments on that subject but perhaps this is close to a human proof.

What I would like to focus on is showing that the periodicity of 8 follows by human proof from the absence of monochromatic triangles. As far as I know this has not been done yet but I think it is in reach. More about that to follow.

2. Philip Gibbs says:

Figure 1 of Aubrey’s paper shows the four nonequivalent ways of 4-colouring a hexagon graph. The two that contain a monochromatic triangle are eliminated within $R_2$ using graph $M$. I want to start from this point and see how much can be deduced without further computer analysis.

The following reasoning is a bit sketchy but hopefully it is clear enough to anyone trying to check it. Please interject if not. As far as I know this has not already been covered anywhere but I please let me know if that is not the case.

What I propose to show is that for any 4-colouring of $R_2$, any sub-ring $R_1$ will be coloured so that it is periodic with period 2 in at least one of the three directions running in the direction of edges, as observed by Tamas.

Take a sub-ring of $R_2$ isomorphic to $R_1$, i.e an infinite triangular lattice in the plane. Consider any pair of colours, say red and yellow, and join up all pairs that are connected by an edge of unit length. This forms a system of lines snaking across the plane.

Because of the limited options for colouring a hexagon without a monochromatic triangle none of these lines can cross, end or split three ways. They therefore form continuous lines in the plane. Furthermore, at each vertex the lines can only continue in a straight line or turn through an angle of 60 degrees (i.e with an angle of 120 degrees between the lines) The two colours red and yellow alternate along the lines.

Consider now the blue and green colours. These can be joined up to form similar lines across the plane. They can never cross the red-yellow lines. In fact the blue-green must run parallel to the red-yellow lines so that the combined system of lines includes all vertices of the plane.

The next step is to show that the lines cannot turn in the same direction twice in a row. Suppose the line of red and yellow colours makes a 60 degree turn, continues straight for $n$ edges, and then turns 60 degrees again. The blue-green line running parallel on the inside of this line is then forced to make similar turns because it runs parallel. However, the number of edges between its turns is $n-1$. This continues with the next red-yellow line and so on decreasing the size of the straight leg by one edge each time. After $n$ steps there is a line that must turn through 120 degrees at one point, but this is already ruled out. Therefore the lines can only proceed turning alternately left and right by 60 degrees between straight sections.

Suppose a red-yellow line does in fact continue in a straight line forever across the plane without any turns. In that case all other red-yellow lines and all blue-green lines that must run parallel to it will also be straight lines without turns. In this case the periodicity 2 in one direction is established.

Otherwise each red-yellow line must have at least one turn left or right. Consider now the unique straight line of edges that crosses the red-yellow line at the vertex where it turns. This line will also cross all the other red-yellow and blue-green lines at vertices where they turn, because they all run in parallel. Furthermore, as you go along the vertices on this line it must alternate between just two colours, since otherwise there will be a monchromatic triangle. This line cannot turn left or right and can only continue in a straight line. By the same logic as before the other colour pairing will form straight lines running parallel to this one and the colouring will have a periodicity of 2 in the direction along these lines.

Therefore the 4-colouring must be periodic in at least one of the three directions of edges in the $R_1$ sub-ring as required.

1. Tamás Hubai says:

You could also start from Aubrey’s Figure 3 and observe that each of the six classes only attaches to itself (exchanging red with yellow and blue with green) when moving one unit to the left or to the right.

Unfortunately we won’t get periodicity in other directions just by excluding monochromatic $\sqrt3$-triangles from $R_1$, as any colouring with alternating red-yellow and blue-green stripes will satisfy our requirements. We’ll need to use that our colouring extends to $R_2$ in some stronger way. But it still looks promising for a human proof.

2. Philip Gibbs says:

I agree. I am trying to think now about what the no-monochromatic-triangle condition implies for the whole of $R_2$ or the part generated by small powers of $\omega$ and $\eta$ this is hard but possibly not unapproachable. What do we get if we join up all edges linking a pair of colours and the opposite pair of colours? the ring can be thought of as a (dense) lattice in 4D. Do we get a covering of parallel 2D surfaces in this space?

A weaker starting point would be to assume a periodicity of 2 in some directions for the whole ring as proposed by Terry Tao.

3. Philip Gibbs says:

The next step is to look at how the possible solutions in $R_1$ can be extended to solutions in more of $R_2$. Consider for example the additive subgroup generated by six complex numbers of unit modulus such as $1, \omega, \omega^2, \eta^a, \eta^a \omega, \eta^a \omega^2$ for a fixed non-zero integer $a$.

Although everything exists in the complex plane it is useful to think of this as a 4 dimensional lattice of points projected onto 2 dimensions. I.e. it is $R_1 \times R_1$, the cartesian product of two hexagonal lattices. This is not the entire ring $R_2$ but it is a substantial part of it. It includes not just the two $R_1$ lattices in the product but also two infinite sets of $R_1$ lattices parallel to the two that pass through the origin. Each of these must be four coloured according to the scheme described in the previous post that follows from the non-presence of monochromatic triangles.

How then can these colourings be combined together? I don’t yet have a complete answer from human logic but here are some preliminaries.

The hexagons in $R_1$ are expanded in the 4D lattice to the cartesian product of two hexagons forming a 4D polytope known as a 6-6 duoprism according to Wikipedia

https://en.wikipedia.org/wiki/6-6_duoprism

The hexagons are composed of six triangles so the 6-6 duoprism is composed of 36 3-3 duoprisms formed from the cartesian product of two triangles.

https://en.wikipedia.org/wiki/3-3_duoprism

(Notice that one projection of the 3-3 duoprism shown in the Wikipedia article is recognisable as a part of the graph $T$ from Aubrey’s paper.

We can try to proceed by analogy to the method that worked for $R_1$. Focus on two of the four colours, say red and yellow and select all edges that join vertices of these colours to form a (disconnected) graph $G_{r,y}$. In $R_1$ this formed unbroken lines across the lattice. In $R_1 \times R_1$ there will be always four edges meeting at each vertex in $G_{r,y}$

The question is, does the graph $G_{r,y}$ split into 2D meshes in the same way that lines formed in $R_1$, and if the same graphs are constructed for other colour pairs are they flat with a 2×2 repetition in one case? I think the computed results of Tamas mean that they are, but so far I can’t see how this follows from simple logic.

4. Marijn Heule says:

The smallest unit-distance graph with chromatic number 5 that I found so far has 553 vertices and 2722 edges. That graph is shown below with a 5-coloring of its vertices. I actually found a dozen different graphs with 553 vertices and reducing them appears challenging. I describe the details about how these graphs were found in a paper that will appear in Geombinatorics XXVIII(1), a special issue dedicated to 5-chromatic unit-distance graphs. A preprint is available here:

https://arxiv.org/abs/1805.12181

1. ag24ag24 says:

Yeah – not Marijn’s fault – he posted an announcement here but it got caught in moderation purgatory. I’ve been in conversation with him as he finalised it and I have a few new ideas, but I’ll wait until his post appears. Incidentally, I have also just posted an update to my paper. Both of our papers will appear in the July issue of Soifer’s journal Geombinatorics.

5. I’ve got the bulk of my paper done after some interesting realizations about dimensional escalation. I feel like I’ve finally developed a very solid understanding for why and how this dimensional escalation happens, and I’ve done what I could to make this easily applicable beyond euclidean unit distance graphs too.

Before I can put it up on arXiv I would appreciate some help with the references, specifically Townsend’s proof that for such region colorings $\textrm{CNP}\geq6$.
I’ve found some free previews from the mathematical coloring book of the part where this is described, but was unable to find Townsend’s work directly anywhere. I would immensely appreaciate being able to link to the original work directly due to the context, does anyone know where I can find it?

If anyone is interested in seeing it before the arXiv upload I can send a preliminary version too.

1. ag24ag24 says:

Townsend, S. P., Colouring the plane with no monochrome unit. Geombinatorics
XIV(4) (2005), 181–193

1. Ah, so that’s why I had trouble finding it, I found his name referred to as Townsend here and mostly elsewhere, whereas the website of this Journal says Townshen and Townshend. Thanks for the pointer.

6. ag24ag24 says:

As threatened, herewith a couple of thoughts inspired by Marijn’s excellent explorations.

The observation at the bottom of page 14 seems particularly important to me. We’ve been having enough trouble just finding graphs with a single pair of vertices that are always different colours in any 4-colouring, and now we have graphs incorporating a whole tetrahedron of such edges – and moreover they all lie on a unit circle, allowing the immediate creation of a 5-chromatic graph (the 553er) by adding its centre. Of course we cannot guarantee that all these four vertices would be different colours in any 5-colouring, but maybe we could build from here to get such a graph. Marijn: could you maybe post a graphic of the 533er in which one vertex with degree 4 is highlighted one colour and its neighbours another colour (and everything else a third colour), so that we can more easily see what is going on?

A second thing that strikes me as useful is how minimal the use of “exotic” edge directions has become. In my paper I noted that initially I tried to use just the 18 vectors what we would here call $i\omega_1 + j\omega_3, -1 \leq j \leq 1$, and even though I achieved really high spindle density I couldn’t get anywhere – and that was just with the search for a graph M, never mind the full N. But now, the 420er that forms the core of Marijn’s graph has not all that many edges that use j=2 (or -2), and the 133er (which isn’t pictured in the paper) that he adds to it at omega_4 rotation has none at all. I think that if we can further minimise the use of exotic directions (and “unplanned edges”) then we might get to a point of being able to understand why we need them at all.

1. ag24ag24 says:

Ah, apologies to Tamas – he of course told us six weeks ago that one can indeed get away with only $-1 \leq j \leq 1$, because that’s what his $V_A$ is (see his post on April 22nd). What Marijn’s graph shows is that if we allow additional powers of omega_3 just occasionally, then there can be rather few vertices with a rotation that involves omega_4 at all.

I’ve encouraged Marijn to attack Tamas’s graph with his methods. A major question would be whether the “halves” of Tamas’s graph, i.e. the sets of vertices that do and do not involve omega_4, can be shruk in different but mutually incompatible ways, as in Marijn’s paper.

1. ag24ag24 says:

OK, Marijn reports the very interesting finding that his clause-minimisation methods can only reduce Tamas’s graph to around 5000 vertices (though he didn’t force it to completion because the runs were very CPU-intensive). Recall that this graph consists of six sets of vertices, defined according to 0 or 1 use of omega_4 and -1/2, 0 or 1/2 use of omega_3. But the graphs from his paper only use two additional sets of vertices, namely using -1 or 1 rotatinons of omega_3 when not using omega_4, this can be reduced by an order of magnitude. I think that’s pretty interesting. Can we find another family to add that would allow a further reduction? We know that just allowing +/-1 omega_3 and also omega_4 doesn’t help, but what about half of omega_4 ? The potential value of these half-angles is that they provide edges that are parallel to the spindling edge in the unrotated graphs. In the case of omega_4 we might want to throw in half an omega_1 too in order to make that true.

7. Philip Gibbs says:

I am trying to understand more about the ways that $R_2$ can be 4-coloured. Tamas has described the colourings of the $R_1$ sub-lattices and I know that apart from the 8-periodicity all other features follow from the lack of a $\sqrt{3}$ monochromatic triangle.

What are the possible colourings for other 2_D sub-lattices e.g. those generated by two powers of $\eta$? Is it true that every unit rhombus that is not in $R_1$ either has 4 colours or 2?

8. I’ve cleaned up and refined a chunk of my SketchUp workspace so I can make it available as a public resource.
A picture of the contents (4 Tesselations so far, along with exclusion zones and some contracted graphs): https://www.dropbox.com/s/zaya72idhdjd2e7/Tessellations%26ExclusionZones.png?dl=0
The model itself: https://www.dropbox.com/s/v8uvwzbiu3srrrk/Tessellations%26ExclusionZones.skp?dl=0
The model can be viewed and used with SketchUp which is available for free.

@ag24ag24: The model contains your pentagonal tiling posted in the 4th thread too, and back then you mentioned having found more tesselations with 16-regular exclusion set sizes, using different tiles like the fattened triangles. Would you mind sharing some of these so I can model them as well?

9. Philip Gibbs says:

I think I know how to get from the lack of the monochromatic triangle to a periodicity of 16 using mostly algebraic methods. It might be possible to get to the known periodicity of 8 by similar means. However, I realise that this is not useful because showing the lack of a monochromic triangle by human proof is already the missing part.

10. ag24ag24 says:

I have a question about the colourings of R_2. Earlier:

Tamas noted that the 9120 colourings of R_2 reduce to 380 if we fix the colours of a triangle, but that if we additionally factor out translations, rotations and reflections we get down to just 22. I’m not seeing why this is so, but that’s not my main question (yet!). My main one is, can we provide a finite graph whose colourings represent these 22 ? My Figure 3 did that for R_1 (except that I only had six options – I’m not quite sure why Tamas has 12), so I’m presuming that it ought to be possible, and that there ought to be ways to extend it to the plane just by overlap of vertices, in the same way that my six options in Figure 3 can only be extended to R_1 by adding copies of the same one of the six.

Hm, the extension of my six is only in one dimension, not both; that presumably explains why Tamas sees 12 colourings of the whole of R_1. But then, as he noted more recently:

the extension to the whole of R_1 cannot be achieved just by adding a few more vertices. Still, surely there must be a finite graph that represents each of the 12 colourings, no? If not, can we say why not?

11. Seems like my previous comment about tessellations and the model got stuck in, moderation purgatory.

In the meantime I’ve modeled the mentioned circular triangle tessellation as well, the model has been updated to include it.

1. ag24ag24 says:

Many thanks Bernhard! I’m not understanding the note “20|24” on the latest tesselation; the concave triangles have 18 too-close neighbours, not 20.

It would be great to understand what deterrmines the chromatic number of the (infinite) graphs that these tesselations equate to. The next one you should do is Pritikin’s almost-6-colouring of the plane, with the small regions ignored; that tesselation requires only six colours even though the exclusion number is 19. In case you don’t have the paper I (hope I!) provide the relevant figure below:

I don’t have images of the other tesselations I found – they were complicated, with some tiles having 15 too-close neighbours and some having 18 – I will need to go back and find my notes when I get home (I’m currently travelling).

1. Thanks, I used an automatic counting method and forgot to compensate for it being 2 off, corrected that.

“It would be great to understand what deterrmines the chromatic number of the (infinite) graphs that these tesselations equate to.”
Here’s what I’ve very persistently observed. Wall of text following.
If we’re looking at an entire space such as $\mathbb{E}^2$ (or higher dimensions) then the chromatic number of a tessellation can be determined by taking a single base cell (of the largest type), using the exclusion zone and contracting all tiles touched by this exclusion zone into a finite graph, then solve it as usual. So it actually seems very simple, once the process is understood.
So far this has always been sufficient to quickly find a k-critical/complete subgraph that agrees with the chromatic number of the entire tessellation.
It has held for all 5 plane tessellations I did so far, and it can be seen in the model and the preview I posted earlier. Though I haven’t yet bothered to single out the critical subgraph for your pentagon tessellation.

I’d wager this also is always going to hold true under same basic circumstances. I think the chromatic number of an euclidean space is probably equal to the chromatic number of $\mathbb{X}_{G_n}(vertex)^{\circ 2}$, which is a n-ball of radius 2. And the exclusion zone of a big tile is basically just an even better approximation.
That being said I do expect this simplicity to break if tiles aren’t chosen with diameter 1.
(Beyond that I conjecture that this may even hold more generally for $\mathbb{X}_{G_x}^{\circ 2}$ where $G_x$ is some specific class of graphs. One of the things I wanted to test, but it’s not exactly high on my priority and curiousity list yet.)

But if we consider multiple not path-connected subspaces, and there is no single region that is large enough for a final pattern to emerge the situation becomes more complicated. One can define such spaces by restricting the exclusion zone on intersections with the space we’re interested in.

One such exception are the n-ball expanded graphs I’ve mentioned earlier and explored in more detail in my paper. They are very clear examples of how special subspaces (and as a consequence very likely the space as a whole) strictly require continuous separated regions, but here more importantly they still behave like their finite counterparts.
That’s because the exclusion zone “echoes” through the n-balls the same way color restrictions echo through finite distance graphs. Really, the only difference is the beginning. Pick a single vertex v, $\mathbb{X}(v)$ will be (n-1)-dimensional, $\mathbb{X}^{\circ 2}$ will be n-dimensional already, no two ways about it either. In fact even with an expanded 2-simplex $\mathbb{X}^{\circ m}$ will cover the entirety of the n-balls after some short and finite m. The same also holds for expanding a moser spindle, and it could no doubt be applied to the 5-chromatic graphs too.
This is why I’m extremely sure that map-type colorings, more specifically Jordan-Brouwer separated spaces are unavoidable.

With that out of the way, back to the question. Due to these traits, for these subspaces (if there’s no region large enough for the final pattern to emerge within) it’s much more complicated to determine where we can cut off the search. For a subspace purely consisting of n-balls as I described we can just contract all n-balls and then search as usual. If the n-balls contain more than one color, regardless of shape, dimensionality or measure, then the contracted node also has to be considered multi-colored.

Now one could also consider more specialized spaces, such as n-balls of different sizes, maybe a subspace with some normally expanded n-balls, and some oversized n-balls, which can’t be 1-colored anymore. I’m not quite sure where we can cut this process off then. There could be further rules to simplify the search depending on the actual size of oversized regions and their connection to the rest, but I’m not sure if this is even a sufficiently interesting case to explore further.

If there’s a maximum over some amount of edges that can even be used for increasing the chromatic number, that could possibly be used to formulate truly general rules of where and when to cut off the search.

“The next one you should do is Pritikin’s almost-6-colouring of the plane, with the small regions ignored; that tesselation requires only six colours even though the exclusion number is 19. In case you don’t have the paper I (hope I!) provide the relevant figure below:”

(The picture appears correctly) While I haven’t read this one specific paper these almost-6-colorings aren’t new to me, I also was quickly able to find the right paper. I think I only skipped over the abstract when I first encountered it. I could swear I’ve seen something damn similar under another name too… I’ll get to modeling that. It should prove far simpler than the exclusion zone of a truncated octahedron which I also started, and almost finished. It just looks a lot less useful in a picture than 2D exclusion zones. I’ll finish and upload that some time as well as a model.

2. I’ve updated the model, still at the same link.
Here’s a preview of the Pritikin tessellation: https://www.dropbox.com/s/yv31dfhtxmvzsak/Pritikin%20Tessellation%26ExclusionZone.png?dl=0

Here’s what I can comment on that so far. First of all I have unsurprisingly found a 6-complete graph after contracting (ignoring the diamonds), and just as with hexagons there’s a set of base cells with which one can very easily tessellate the entire space, it consists of 6 heptagons and 3 diamonds.
I’ve taken a look at the exclusion zones of the diamonds as well, and they have little overlap, as expected.
The exclusion zones of the heptagons on the other hand have very extreme overlap, most of the space is double or triple excluded, and the amount of space that’s neither excluded nor colored by a certain color is extremely small, but there still is a 2-dimensional measure of such regions.
(The circular triangle tessellation was of particular interest to me here because there is absolutely no 2-dimensional area of wiggle room for any color. Except the boundaries, every last bit of space is either colored or excluded by any given color.)

3. ag24ag24 says:

Here’s one of my more complex tesselations, from memory (and it’s not my best-ever drawing, apologies). I may have misremembered it, since as far as I can tell it has an exclusion number of 17 for bot types of tile – but hey, that’s not bad 🙂 I show rhe exclusion set for the more difficult tile.

2. ag24ag24 says:

Apologies – this may be because I’m misremembering my construction, but I don’t see a way to fix it – the oddly-shaped pentagons in my tiling need to have one corner clipped in order to stay small enough and also far enough away from one other copy, so the actual sizes of the exclusion sets are 18 and 19. I’ve updated the image accordingly.

1. Not sure what you mean with the corners, after reverse-engineering the geometry I didn’t have such a problem. But I did pretty quickly find the 19|18 edges you mentioned.
I should probably adopt the ‘exclusion set’ naming scheme since it’s clearer, will probably do that in a future update.

But I’ve got it done now. It was certainly a bit more challenging, but it was a decent learning experience both for the math behind it and using SketchUp in general. Here’s the preview: https://www.dropbox.com/s/nfthpkyyoeowois/DGMTessellation.png?dl=0
And as usual the model has been updated too.

I wasn’t sure how to name that tesselation however, do we have a specific name for it?

2. ag24ag24 says:

Thanks again Bernhard. Yeah, I had miscalculated some of the distances – I now believe that the edges that meet at the degree-4 vertex can indeed be curves of radius 1 all the way to their other end, whereas earlier I had calculated that that would make the pentagons have a diameter slightly greater than 1. Thus, the real numbers are indeed 18 and 17 as in your figure. I have updated my figure accordingly.

I’ll try to get time to recreate my other promising tessellation today or tomorrow.

Meanwhile, though, I wonder if we can prove your empirical finding that when the infinite graph of a tiling’s too-close pairs is k-chromatic, it always has a k-chromatic subgraph whose vertices consist of some tile and its exclusion set. (I’m pretty sure that that’s equivalent to what you said – do you agree?) It would certainly be a terrific step forward in looking for better tilings if we could either prove this or identify a way to construct counterexamples.

3. Yes that’s what I meant. I’d say contracted graph, not subgraph since it technically isn’t a true subgraph, nor does it have unit distance edges, but otherwise I agree. To prove that we should probably have some rigorous and specific notation of the contract process. Here’s what I think on that front.

Let cc(a,b) be a boolean function to determine whether two vertices are path and color connected, that is there exists a path between a and b, and all other vertices on this path have the same, single color as a and b.
$cc(a,b)=\exists f:[0,1]\rightarrow\mathbb{E}^n\mid\begin{matrix}f(0)=a\\f(1)=b\\\end{matrix}\land\#c\biggl(\bigcup\limits^{1}_{j=0}\biggl\{j \in \mathbb{R} \mid f\biggr(j\biggr)\biggr\}\biggr)=1$.

Split the space into continuous color regions based on path/color connectedness and whether they are part of the same graph component.
$CR_i = \forall (a,b) \in \mathbb{E}^n\{cc(a,b) \land \mathbb{X}^{\cup\circ\infty}(b)\}$.
(The graph component part always evaluates to true for 2 or more dimensions. I mainly keep it here for the sake of generality, as looking at other types of infinite graphs with the same function could be useful later on.)

The exclusion set of $CR_1$ are all $CR_i$ that have a vertex which is an element of the exclusion zone of $CR_1$.
$\mathbb{X}S(CR_1) = \{ CR_i \subset \mathbb{E}^n \mid \exists (a \in CR_i)\in \mathbb{X}(CR_1)\}$.
And $\mathbb{X}SN(CR_1) = \mathbb{X}S(CR_1)+CR_1$.

Let $cv(CR_i)$ be the center vertex of $CR_i$ (or well, any single vertex).

Now we can start building the contracted graph. First its vertices:
$V(GC_{CR_1})= \{CR_i \in \mathbb{X}SN(CR_1) \mid cv(CR_i)\}$.

And finally the edges:
$E(GC_{CR_1})= \{ CR_{i1},CR_{i2} \in \mathbb{X}SN(CR_1) \mid\exists (a \in CR_{i1}) \in \mathbb{X}(CR_{i2})\}$.

That was quite a bit of LaTeX and I more than likely have the one or the other error in there, and some of the symbols and letters could probably be picked better, but it should still make the process clear enough.

So, counterexamples. There’s definitely the size of the considered $CR_i$. Take a 8-chromatic square tiling and let $CR_1$ be a tiny miscolored region (or vertex, or line) in the center of one of the edges between two squares, raising the chromatic number of this infinite graph to 9. The contracted graph $GC_{CR_1}$ will however only be 7-chromatic, a contradiction to the general assumption that a contracted graph has the same chromatic number as its infinite origin.

If my JB region theorem is true we can dismiss the idea of using vertices or lines, as the contraction process only needs to hold in efficient tesselations. This still leaves us with at least the size problem. Are there any tesselations with tiles of only diameter 1, or very close 1, for which this assumption is also false? If not how do we prove this assumption is correct and under which circumstances exactly?
A side note here, earlier I said taking the biggest tile. Actually the contracting to receive a graph with the same chromatic color has so far also worked for the smaller tiles in efficient tesselations.

We should probably look if there are proofs of different results that could be relevant. I’ve seen countless examples of using tiles at diameter 1, that only barely fit by making the regions partially open, and partially closed, such as [0,1) on a numberline. All of the tesselations in the catalogue I build are constructed this way, except the hexagon tesselation. In 3 dimensions we have the bitruncated cubic honeycomb with the same diameter 1…
Yet I’ve never actually seen concrete proof that these diameter 1 constructions are always superior to ones using smaller diameters. I’m not sure if I missed it, or if there really is none.

One thing that I did a while ago was looking at the exclusion set of a hexagon as we scale the tesselation down. So if we drop the diameter down to 0.75 the exclusion set cardinality goes up by 12. As the hexagon is scaled down to approach being infinitely small, the exclusion set size approaches $\aleph_1$, and more specifically with a measure it approaches $2\pi u^1$. Clearly for all of the unscalable tesselations the exclusion set size explodes immediately upon scalin down. But… what to do with that, if anything? It strikes me as possibly significant that for a measureless vertex “tesselation” the exclusion set size actually does have a measure, whereas for any n-dimensional tiling with a measure the exclusion set size is finite, but I have no idea if and how a proof might be derived from that.
Aside from that I have no idea about further counterexamples.

The other and last idea is the one I had somewhat indicated earlier, we might be able to expand on the De Bruijn–Erdős theorem, so we don’t just state that there is a finite k-critical graph, but also how far to look. Maybe a proof that for all/specific infinite graphs the chromatic number and the persistent “tiling” emerges within $\mathbb{X}^{\circ 2}(vertex)$ is easier to reach, and we can go towards graph contracting from there. Still, that’s an n-ball of radius 2 for euclidean spaces, wheras the largest possible exclusion zones only approach n-balls of 1.5 in diameter, so that’s a big gap. And I have no good approach to any of these ideas in mind yet.

12. The wiki page needs updating to list the 553-vertex graph. The 5-chromatic graph with the fewest vertices mentioned is the 610-vertex one.

1. Philip Gibbs says:

Done now.

13. ag24ag24 says:

OK, here’s a depiction of my other reasonably-efficient complex tiling. There are three types of tile in ratio 1:3:6 with exclusion number 18:18:15, thus averaging 81/5. I hope the image is good enough to convey the appropriate curvatures.

1. Huh, interesting. And the pictures are more than enough to convey everything I need, I’ve already got the base tiling done. But I’ll probably take a while longer to finish and upload this one. I’ve got enough experience and data now to make a plugin which will create the exclusion zones at a single click, which will save me a lot of time later on. And I might be able to then later expand on that plugin to create 3D exclusion zones at a moments notice as well, which I’ll no doubt need for the Phelan structure once I get to it, and other 3D honeycombs. I have the Weaire-Phelan base tiling done too (since there were public assets I just had to take and clean up a little), but the exclusion zones become exponentially harder to deal with in higher dimensions, so that won’t be done any time too soon.

On another note I think we also have one of the puzzle pieces for a proof that can take us from JB regions to lattice-sublattice coloring schemes here. One thing all of these efficient tilings have in common is that they have a boundary defined by straight lines or unit distance arcs. So far all possible tesselations that use some other kind of boundary can be reduced to one using only straight lines and unit radius arcs.

1. ag24ag24 says:

Hm, actually on staring at this tiling more I see that it has a problem. Looking at the lower-left labelling (the one that shows the exclusion set of the entirely convex tile): the extension of the horizontal line between that tile’s lower vertices passes between the neighbouring tiles’ opposite corners, which means that those opposite corners (and, thus, the tiles labelled 1 that lie beyond) are actually a hair closer than 1 to both the entirely-convex tile and the one below it. I think the best we can do to fix that is to slightly deform the whole tiling by rotating all the four-tile triangles, but even then we only get half of these overlooked exclusion pairs back.

Ah well! So it is increasingly seeming that the uniform pentagonal tiling with exclusion sets of size 16 is particularly special – though not quite special enough to give a 6-colour coverage. Like you I am beginning to feel that a proof that any tile-based covering (scaleable or not) needs seven colours may be within reach. If not, at least it may be that an attempt to derive such a proof would be a good way to identify additional tricks.

2. I’ve been dabbling with my plugin a while and some SketchUp quirks prevented me from getting as good a result as I wanted, but it still made the process easier on me. So I got back on this tiling now.

I had been able to confirm the initial mentioned conflict early on, but only got around to working on it with the plugin now. With this conflict I think the exclusion set sizes are 17/24/20, pentagon/Reuleaux triangle/concave triangle. Changing the Reuleaux triangle to a regular one solves all it’s conflicts, but creates a lot of new ones, 17/18/24. Since the triangles are present in a ratio of 1:3 we remove 6 edges from the contracted graph, but gain 12 new ones, so clearly the arcs win over straight boundaries here.

I’ve also attempted your rotation, that is I think rotating all of the 4 triangles as a group. while it also allows to solve some conflicts, I think there’s then a problem with the pentagons. They already contain multiple corners at unit distance, and rotating the triangles then creates some empty space we can neither fill with the triangles anymore, nor the pentagons. Am I missing something?

And if the answer to tilings is indeed seven I’m certain it’s in reach, and all it might take is a specific, lucky realization, but who knows. It’s bugging me that I can’t find the source of the lattice-sublattice claim, this would most likely give some nice inspiration.

2. Philip Gibbs says:

I did some random trials to try to find solutions for 6-colourings. Of course it never works but here is a sample pic (fingers crossed)

My inclination to tackle this topologically first. You need a tiling of pentagons each joined by edge to five other pentagons. A few squares or triangles could be added but topologically that is probably unhelpful.

Each vertex will have three or four edges and faces meeting. More is possible, but possibly not helpful. The average number of edges per vertex is 10/3 so two 3-edge vertices for every 4-edge vertex. There are lots of topological ways to form such tilings.

Each face will have to be surrounded by five faces of differing colour, but there is one more constraint. You have to avoid a combination such as red-vertex-green-edge-red-vertex-green. Is this topologically possible? If not there may be no point trying to find a good geometry.

1. Philip Gibbs says:

I mean that this is not allowed because however you position or curve the edges it fails to be a valid colouring

2. So far the tesselation with the lowest exclusion set sizes seem to have pentagons and the only 7-critical one we know of is the initial Pentagon tiling by De Grey which I modelled. So I’d also say that squares and triangles likely aren’t helpful.
Though there’s still the hexagon tesselation. While it’s true that its contracted graph has 7-complete sugbraphs, and it has a bigger exclusion set size, it is also the only 7-chromatic tiling I’m aware of that’s uniformly scalable.

Looking at your second picture, if we analyze this specific example with the exclusion zone we find that the exclusion zones of the two outer pentagons both cut through the center edge and into the other pentagon of the same color and orientation. Using a straight edge here means we actually have to recolor two tiles. Using a Reuleaux arc in either direction allows us to resolve one of the conflicts, but we still have to recolor one of the tiles, so no valid coloring as you said.
Not yet sure what to do with this. Maybe, if we could make a proof that these or those types of polygons aren’t helpful (triangles, squares, depending on perspective maybe hexagons), then take the arcs into account… this could be part of a final contradiction. But I’m not really seeing it come together just yet.

If there’s some sort of efficiency curve then there pretty much has to be a 7-chromatic square tiling too, and I think I know how to build it.

It’d also be interesting to try and see some regular pentagons with Reuleaux arcs. There might be some more 7-chromatic tilings to be had there, but I’m not sure.

3. Philip Gibbs says:

The smallest size at which I find 7-colurings with squares is this one

4. Philip Gibbs says:

Actually this one is smaller, but with a tight distance.

5. Huh, that’s not what I thought about at all. The other square tesselation I’ll include in the next catalogue model update is just the normal regular square grid, with half of the rows shifted. The result is a tesselation that’s pretty much the same as the hexagon tesselation, just not scalable.

But I’ll definitely try modelling these too once I have my plugin ready. They might help in forming a conjecture about reducing edges in certein tilings. Nice piece of work I didn’t even think about remotely.

6. Philip Gibbs says:

I will look forward to seeing that.

I also missed a trick in not trying non-square patterns, so missed this simpler example which is probably already known

7. ag24ag24 says:

Lovely stuff Philip! Yes, the red-green-red-green thing you mention, which I ended up calling a convexity conflict, was the constraint that directed much of my explorations over Christmas leading to the tilings I’ve posted here. I definitely didn’t get to the point of feeling I’d exhausted the search space, but I also didn’t get far seeking a rigorous description of that space. One thing that daunted me was the realisation that we can actually allow hexagons (or higher) and still not necessarily need seven colours, if we have one or more colours represented only by small tiles arranged so that nearest-distance pairs of tiles lie entirely within a unit circle and the next-nearest distance is at least 1. These small tiles don’t need to be fantastically small – consider, for example, circles of diameter 0.2 placed on a triangular grid of edge 0.8 – so I don’t think such tilings can easily be shown never to be 6-colourable.

8. ag24ag24 says:

In particular, we can’t just say that any putative 6-tiling of the plane that contains two tiles of the same colour lying within a unit circle can be converted to one that doesn’t just by changing a stripe of points between them to their colour. To see this, arrange four small tiles (all the same colour) in a diamond such that two are within a unit circle and the exclusion zones of the other two meet between the first two. For example, consider small circles centred at (+/-0.4,0) and (0,+/-1).

9. Philip Gibbs says:

I am sure you are right. It is hard to eliminate special cases. Even if the problem can be reduced to topological colouring problems these may be similar to trying to prove the four-colouring problem. It may look like there should be a simple proof when in reality it requires a long search through cases.

Sometimes the best that can be done with these combinatorial geometry problems is a reduction to a series of conjectures and bounds conditional on assumptions that may or may not be valid. Than at least other people can pick up manageable sub-problems and work on them.

10. “Sometimes the best that can be done with these combinatorial geometry problems…”

I think so too. The thing is, even though we already have many nice papers, conjectures, and even solid results for certain assumptions, the information is yet to be neatly organized. I wanted to grab the paper that proves that a lattice-sublattice coloring scheme necessitates the chromatic number 7, but I couldn’t remember where I read this for some time. And just recently I did. It’s mentioned in Coulson’s paper on convex tilings: http://www.austms.org.au/Publ/JAustMS/V77P2/pdf/a83.pdf

“Any lattice-sublattice colouring scheme for $R^2$ must use at least 7 colours to have an excluded distance.”
There’s a glaring problem with this claim in that paper. I find it is neither explained nor referenced in any way. And since I can’t find the source of this claim I have to retract my statement, unless someone else manages to find it.

So I think we should have a section in the Polymath wiki with a neat list of such conjectures and theorems, brief descriptions of their statements and implications, and of course verifiable references. Then we could also add conjectures there which have been made in these Polymath threads, and a section on the upper bounds might be good too. There’s still a lot of time left for this project and I deem it very well possible that in this time frame researching the upper bound can later give concrete insights on the lower bound and finite graphs as well.

11. Philip Gibbs says:

The topological structure of the colouring I posted above can be better understood by joining up it dual graph like this

This gives a grid of triangles and quadrilaterals such that every vertex has a valency of five. If we aim to 6-colour the plane we must first colour the vertices so that all five vertices joining a given vertex have different colours. Also the vertices of each quadrilateral must be coloured with four different colours. Finally we must avoid the G><R structure. These are tight constraints. Is it ever possible? If it is we may be able to fix the geometry to give a 6-colouring.

Observe that the grid is actually topologically derived from the usual tessellation of equilateral triangles with edges removed to reduce valency from 6 to 5 for every vertex. Is this always the case? What if we assume it is?

I think this pentagonal tiling posted by Aubrey has the same general type of topological structure but with different links removed, so we would be covering a lot of ground if we could analyse all possibilities.

12. Philip Gibbs says:

(reposting due to two images triggering moderation)

The topological structure of the colouring I posted above can be better understood by joining up it dual graph like this

This gives a grid of triangles and quadrilaterals such that every vertex has a valency of five. If we aim to 6-colour the plane we must first colour the vertices so that all five vertices joining a given vertex have different colours. Also the vertices of each quadrilateral must be coloured with four different colours. Finally we must avoid the G.R|G.R structure pictured above. These are tight constraints. Is it ever possible? If it is we may be able to fix the geometry to give a 6-colouring.

Observe that the grid is actually topologically derived from the usual tessellation of equilateral triangles with edges removed to reduce valency from 6 to 5 for every vertex. Is this always the case? What if we assume it is?

I think the pentagonal tiling posted by Aubrey on June 5, 2018 at 10:42 am has the same general type of topological structure but with different links removed, so we would be covering a lot of ground if we could analyse all possibilities of this type.

14. ag24ag24 says:

I have a very general question about the whole family of problems we are discussing. I’m fairly sure I have never seen it stated, let alone proved, that the finite graphs and periodic coverings that everyone has always used as proofs of (respectively) lower and upper bounds must always combine to give an exact value. In other words, is it proven that for any positive integers n and k there is always either a finite k-chromatic unit-distance graph in R^n or else a periodic k-colouring of R^n excluding distance 1 ?

1. I’m not sure how right I am, but I’ll risk and try giving an answer anyway.
(I’ll also try to write it so it’s useful for others as well.)

The proven De Bruijn–Erdős theorem, given the axiom of choice, does indeed always grant us the existence of a finite k-chromatic unit distance graph not just of $\mathbb{R}^n$, but for every type of infinite graph.

If I got all of my information straight the upper bounds are, or were by far not so clear cut yet. When I began working on this problem last year I think we pretty much just knew that certain restrictions would raise the chromatic color, such as a measurable coloring for 5 colors, Jordan regions for 6 colors, a lattice-sublattice scheme for 7 colors. There’s been many papers on what happens if we grant these restrictions, but there were none proving them to actually apply. Of course now that we have an actual finite unit distance graph we know that it’s at least 5 either way, not sure what this would mean for the measurable case.
So for example Woodall, Townsend and Coulson have worked on assumptions of Jordan boundaries or the likes, then proved 6 colors for this case, but never actually proved anything about the necessity of this assumption, or lack thereof.
So the official state of things is, maybe we need Jordan regions but the chromatic coloring is actually 6 through some miraculous coloring no one has thought of. Or maybe there’s even a non Jordan bounded coloring with chromatic color 5.

And then we also know about the infinite graph which is (in my opinion clumsily) described on the wikipedia page.
It’s defined on $\mathbb{R}$ and its exclusion zone is $\mathbb{X}_{G_M}(v) =\bigcup\limits^{}_{(a_1, \ldots ,a_n) \in v} \{q\in\mathbb{Q}\mid q\pm \sqrt{2}\}$
I’ve gotten this wrong before given the less than impressive descriptions I found but here’s what I think is the case: This infinite graph has a clear 2-chromatic matching iff we use the axiom of choice. That’s because the graph components themself are non-measurable. Since we basically can move only through addition/subtraction, and the only numbers we have to do so are the rationals, and integer multiples of $\sqrt{2}$ which is algebraic, we are constrained into a field of algebraic numbers. For instance there is no path from 0 to $\pi$. If there were then $\pi$ would be algebraic. Our graph components are sets of algebraic numbers (I think, but clearly this graph is not connected either way) with some offset, our “tiles” are sets of rational numbers (I know) with some offset.
Now this infinite 2-chromatic coloring is non-measurable and everywhere dense, so it’s not just the case that a measurable coloring, or a solid interval, is unnecessary, it’s actively detrimental. Clearly both colors have to be densely present throughout the numberline so a solid interval or measurable coloring will contradict this.
So then if we do not use the axiom of choice the chromatic color of $G_M$ is $\aleph_1$, even though we can take any finite subset and 2-color it.

And we generally didn’t know for the past decades if maybe such a non-measurable coloring actually might exist for the plane.

The bulk of my work throughout the past 6 months was focused on proving that Jordan regions are unavoidable and closing this small but critical gap in between the other work done by many mathematicians throughout the years.
I had made many somewhat clumsy attempts in that time, some posted in earlier threads of this Polymath project, all of which felt right, but just didn’t have a solid proof behind them. That was up until a month ago when I realized that certain n-ball expanded graphs behave much like their finite counterparts, and that these n-balls can be proven, through iterations of the exclusion zone, to strictly require a solid region coloring, through a generalized and relatively simple to demonstrate contradiction.
While it is relatively simple to demonstrate and prove, it’s also an extremely specific example and without having a clear definition of the exclusion zone and how it iterates it’s not coming together.

I’m pretty sure I was the first to discover this, since the implication is indeed that for $\mathbb{R}^n$ there exists both a finite unit distance graph and a Jordan region coloring that agree on the chromatic color and which give a provable definite answer (taking the De Bruijn–Erdős theorem and the axiom of choice into account), thus granting both $\textrm{CNP}\geq 6$ (taking Townsend’s and Coulson’s work into account, but actually Coulson only talks about convex tilings, so I’m not sure if his work is actually relevant towards the 6, or if it’s just Townsend.)
Another implication is that analyzing when a space becomes k-chromatic can tell us something about the conditions of when a finite unit distance graph can become k-chromatic, albeit I know very little about this as of yet.

I’ve mentioned earlier I wanted to get a paper about this on arXiv, but I haven’t yet managed simply due to a lack of knowledge about the processes, and the lack of an affiliation with any recognized group/organization also isn’t helping, but I’ll get there eventually.
In the meantime here is the current version of my paper: https://www.dropbox.com/s/1v624wnwh56g162/Exclusion%20zones%20in%20infinite%20graphs.pdf?dl=0

It’s a work in progress, I need to improve the structure, the language and there’s still notation missing, such as the actual full LaTeX description of graph contraction based on the exclusion zone. But the main part, the contradiction proving necessary Jordan-Brouwer space separation is already in there. I hope I got this sufficiently right, and that this helps clear things up a little.

2. I suppose the question you wanted to pose is whether there is a finite (k+1)-chromatic unit-distance graph or a periodic k-coloring excluding distance 1, right? Or equivalently (assuming ZFC and using de Bruijn-Erdos), whether the existence of a k-coloring implies the existence of a periodic k-coloring. AFAIK, this is not known.

15. @Philip Gibbs I’ll answer here because the other reply chain turns a bit long.

Here’s a picture of the dual tesselation of the mentioned De Grey tiling:

It’s not quite the same, even though it does contain triangles and quadrilaterals. At a glance what I notice in your picture is that the triangles and quadrilaterals kind of construct separate paths, which looks interesting, though I don’t know what to make of it, or how to try deriving an actual tiling or contradiction from it.

1. Philip Gibbs says:

Here is how the De Grey tiling can be seen to fit on the triangular lattice

My idea here is that there is a generic class of tilings of this form and the colouring is very constrained. It might be possible to analyse the whole class and determine whether or not it can yield a six colouring

1. ag24ag24 says:

I too am getting quite hopeful about all this. The parallel with how the four-colour theorem was proved seems very valid, and I have the sense that the number of cases in our case may be much fewer, few enough for a human proof. That hunch is based on the observation of the maximum width (is that the right term? I mean, minimum separation of parallel lines between which something can fit) of a 6-colourable patch of a given tiling, for each of the tilings I’ve explored. It’s easy to make 6-tilings of patches with arbitrary diameter and width as large as almost 4 – the simplest I know is to take four columns of the Pritikin tiling, with the diamonds up the middle, and remove the diamonds and restore separations by fattening all the diagonal (i.e. short) edges of the pentagons they used to abut – but I don’t know a way to get the width above 4. I haven’t tried to convert these Euclidean widths into graph-theoretic distances in the tiling-dual graphs, but I think it should be possible to exclude quite small finite subgraphs of 5-regular (or, perhaps, any) tiling-duals by checking all colourings within a given graph-theoretic radius from a starting vertex for adherence to the constraints we have enumerated.

One variation that may make this easier is to add to these tiling-dual graphs the edges that correspond to tiles meeting at a point. Colour the original edges black and these new ones white; then we know for a start that the total degree of the vertices averages at least 6 but no vertex can have a black-degree exceeding 5 (if we ignore for now the “close, small tiles” problem I mentioned yesterday).

2. Philip Gibbs says:

I am trying some computer searches which I thought would quickly rule out solutions. Instead I am finding solutions for grids up to 6 by 6 like this

I have not used periodic boundary conditions so ignore the edges. I will see if I can find a solution that is periodic and we can then see if it can be used to colour the plane or whether some geometric constraint stops it being possible.

It would be sensational if complete solutions leading to a 6-colouring of pentagons tiling the plane exist, but I would think that one of us would have found one by now if it did. What I am finding is that they are harder to rule out using just topology than expected.

3. ag24ag24 says:

Philip, this is extremely cool. I had totally not thought of the transformation to an edge-depleted ttriangular grid, and yes, that clearly makes computer search far more tractable. I totally agree about looking for a periodic solution, and actually I would not be surprised if they exist, because I remember finding tilings that I was fairly sure could only be excluded by appealing to the convexity conflict constraint. What do you think about enhancing the search by addition of edges (of a different colour) that denote pairs of tiles meeting at a point? Or even, can we actually infer the pairs of vertices that equate to such pairs of tiles, just from the local topology of the existing graph?

4. Philip Gibbs says:

I am working on looking for periodic solutions now. I will make the topology have a small period but allow for the colouring to have a larger period. Once you start colouring there is not much choice because two monochromatic nodes must be separated by at least three edges on this graph.

Tiles meet at a point in the middle of the four sided diamonds. Identifying violations of the convexity constraint requires looking at edges that join two such diamonds

5. Philip Gibbs says:

I searched for periodic solutions of this type and could not find any yet. There is scope for more optimisation so I will not give up. There seems to be quite a wide range of possible outcomes to the question: can a 6-colouring be constructed with pentagonal cells? It might be that there are periodic solutions or there may be only aperiodic solutions. Think Penrose tiling. There might be solutions which have a periodic geometry but the colouring is aperiodic. Such exotic scenarios seem unlikely but less so than you would guess a priori. Searches should not make too many assumptions.

Whatever the answer, it does look like it may be possible to colour a surprisingly large area (e.g. a big square or rectangle) with six colours. An interesting question that can be tackled computationally is: how big a rectangle can be 6-coloured? Perhaps we should set some records for that. In previous random trials I was looking for periodic solutions but that is looking like a bad ansatz. I am now thinking it may be better to grow solutions outwards. Another exotic outcome would be that there exist solutions of arbitrary size but no infinite solutions. I’ve no reason to think this would be the case but it is possible. I think we need more numerical evidence to get a better feel for what might be the nature of the solutions we are looking for.

6. ag24ag24 says:

This is all extremely exciting. How are you checking that a topology really can be realised geometrically? Do you have an algorithm for automatically drawing the actual tiling that corresponds to an admissible dual graph? – that would be mighty impressive in itself.

7. Philip Gibbs says:

I have been thinking about that and the conclusion is not encouraging. I worked out that 4 out of 5 edges need to be arcs. Each one defines two pairs of points that must be a unit distance apart. That gives four constraints for each vertex which is twice the number of degrees of freedom.

I did not realise there would be so many geometric constraints. Unless there is a lot of redundancy (or I made a mistake) it is not going to be possible to construct the solution, so I suppose this is where the whole idea falls apart.

8. Philip Gibbs says:

No wait, I am confusing vertices with those on the dual graph, we might be OK. I need to work through an example to be sure.

9. ag24ag24 says:

Hey, well, even if you do find that things break, there’s a good chance that they will break provably, so we can eliminate types of 6-colouring and then move on to cases that are not just pentagons, etc – either way I’d say it’s very exciting. You are definitely already way ahead of where I got to with pen and paper. Go Philip! 🙂

10. Indeed, whether the final answer is 6 or 7, having these last few pieces towards a final and definitive answer for the plane would be phenomenal either way. The type of work you’re doing is one I considered possibly taking up myself many many months in the future, so seeing this come together so quickly is neat.

What I want to ask is, have you already found some other geometrical constraints, or are there some conjectures that as of yet are missing a proof?

11. Philip Gibbs says:

Thank you for the encouragement. It helps!

I think it will be difficult to rule out all cellular 6-colourings. If the cells are all very small they can have any number of sides without contradictions. I don’t know how to rule out that kind of solution. However, if the cells are large they will have to have at most five sides each touching cells of different colours. If we assume that this is the situation then we can make progress.

Under this hypothesis we know we will get vertices of valancy four of more. This picture illustrates what happens.

Cell A touches cell B at a vertex V with valency (at least) 4. If B is a pentagon there must be another cell C touching B with the same colour as A. This necessitates an arc of radius one between B and C joining vertices W to U. The distances VU and VW shown in blue must be one.

So this provides two geometric constraints on the positioning of the vertices. The trouble is that this happens a lot. There must also be another cell touching A with the same colour as B, so that is two more constraints. The other cells touching at vertex V each provide two more constraints. There are only two degrees of freedom to position each vertex. With counting arguments there are potentially more constraints than degrees of freedom. I say “potentially” because some constraints can be redundant where two of the blue edges coincide, but this imposes more difficult topological constraints. This is what needs to be investigated further.

12. ag24ag24 says:

Right. My feeling is that your current focus, where all tiles are large pentagons, is the best place to start because there is a good chance of demonstrating that it is impossible, albeit only by careful computational (though maybe ultimately human-comprehensible) analysis. If and when we get such a proof, the good news is that there are natural, small, next steps towards increasing generality – first to let the tiles be quads or triangles but still constrained to be large – then maybe to identify a conversion of small-tile tilings to large-tile ones – then maybe a conversion of what I’ve been naively calling Cantor-like partitions to nice tilings – etc. The value I see in small steps like this is that at each stage we have a relatively narrow window of new opportunity, such that if a 6-colouring is possible then we will be guided towards it.

13. Philip Gibbs says:

I think that is a reasonable assessment.

I have been busy today, but a few more thoughts on the counting of constraints. If it is assumed that all cells are pentagons then it is easy to work out ratios of geometric structures. For every three vertices there are 2 pentagons, 5 edges, 1 4-valence vertex, 2 3-valence vertices, six degrees of freedom and up to 8 geometric constraints ( a constraint being two vertices which must be unit distance apart). However, we can run into trouble if there are more constraints than degrees of freedom, i.e. more equations to solve than variables. So redundancy is needed.

In a triangular lattice there are three unit length edges per vertex, not two, so that is one possible source of redundancy, but fitting the vertices to a triangular lattice does not seem very viable. Luckily there is another option. Each pentagon has on average 2 4-valence vertices generating up to 4 constraints on diagonals or edges of the pentagon, so there is plenty of opportunity to make constraints coincide. If this is done on average once per pentagon we get the required balance between constraints and degrees of freedom.

The difference between what is required to produce a solution and what is possible seems very close still.

14. ag24ag24 says:

Yes – coincident constraints seems to be the key – and yes, the gap is small. But yet, I’m still thinking that if the gap cannot be closed then we should be able to enumerate cases.

Rather than seeking a patch as large as possible, maybe it’s better to seek small patches in our existing tilings that have a neighbouring tile with no admissible colour. Such patches define additional topological constraints, since the patch itself translates into a particular topology (or maybe multiple alternative topologies, but I suspect not) for the dual graph. For my pentagonal tiling there is a nine-tile patch with only two essentially different colourings and a neighbour that is uncolourable in either. If other cases are of that order, seems to me that it might be possible to enumerate a minimal set of such prohibited patches that any tiling of the whole plane must contain, giving a proof by contradiction.

15. “I think it will be difficult to rule out all cellular 6-colourings. If the cells are all very small they can have any number of sides without contradictions. I don’t know how to rule out that kind of solution.”

Right, I think I’ll start tackling this in earnest now, we should have enough data to build a good intuition on the size problem. I see a number of ways to try and rule this out, but I’m not yet sure what the smartest path to take is.
We can rule out sizes close to, but not exactly 1 very easily, as all of our efficient tesselations (except the hexagon grid) explicitly rely on diameter 1 constructions with partial boundaries. Without this, exclusion zones reach past all adjacent tiles, which in turn creates larger complete contracted graphs. Aubrey’s so far most efficient tesselation immediately jumps to 8 complete if we go just a bit below diameter 1.

To be exact, if we’re close to 1, but not at 1, then we can find complete contracted graphs in a different way, using dual tesselations. I might write something about this some time later.

If we go significantly smaller then the dynamics change drastically however. The size of complete graphs goes down a lot, and likewise the vertex degree goes up. This behaviour is pretty much a gradient between the finite and fully tiled case.

Question for Philip: Could you give an example of how very small cell sizes come out without contradicitons in your current construction? This might give me a hint where to look.

16. Philip Gibbs says:

In my construction I start with a triangular grid and reduce valency from 6 to 5 for each vertex by removing edges. This is then used as the dual graph of a possible colouring of pentagonal cells/tiles. It is important to state that this does not cover all possible ways to divide the plane into pentagons. In particular, every pentagonal cell will have at least one vertex with a valency of four in this construction. This means that the cells must either be small enough to allow surrounding cells to fit within a diameter of one, or the cells themselves must all have a diameter of exactly one. I am assuming the latter. I am not sure if this answers your question.

The aim is to enable a systematic survey of a wide range of possible tilings of the sort that Aubrey was looking at. It may be hard to rule out possibilities for tilings that do not fit this construction. My hope was that this might actually provide a 6-colouring, and if not it might be possible to take it to higher dimensions and succeed there.

However, the arguments about constraint counting are possibly more general and may be useful for impossibility proofs beyond this construction.

Your methods seem promising and I will try to understand them better once you have written up. I understand that Woodall, Townsend and Coulson have proofs that 5-colourings are not possible with cellular divisions of the plane (i.e. where the plane is divided into areas bounded by Jordan curves such that the interior of each area is monchromatic) Unless they made extra assumptions their argument must apply to small cells. I wonder if this aspect of their work can be adapted to say something about 6-colourings with small cells. I realise you have probably already looked at that.

17. Philip Gibbs says:

Here is an example where I had a good base topology for the dual graph, so I started to draw the cells and their constraints, not to scale. The vertices have to be moved around so that every pink line is of unit length. With only these cells drawn it is already seen to be impossible in this case.

18. Philip Gibbs says:

I think Aubrey is right that we should be able to enumerate cases for small configurations and build up from there. We can start with some reasonable set of assumptions, e.g. I would assume that all tiles are pentagons of diameter one and that all vertices have valency three of four. I think we now have a good feel for the topological and geometric constraints and can start working by hand. In that case it is not necessary to restrict to the grid topology.

If these assumptions are enough to make progress we may then be able to complete the 6-colouring cellular case with a combination of a few generalisations and Bernhard’s methods. It is worth a shot.

As a starting point we can enumerate the possibilities for one pentagonal tile depending on the valencies of its vertices and the different colour combinations. The geometric constraints can be worked out for each one and that will tell us a lot about its shape. This should provide a set of single tile pieces that can then be fitted together like a jigsaw puzzle, perhaps. If the number of possibilities explodes we will have to return to the computer.

2. Tom Sirgedas says:

Here’s a possible simple tiling of the plane. Most of this discussion is over my head, so I’m sure I broke some rule!

1. Philip Gibbs says:

Nice try but sadly you broke the cardinal rule three times here

The alternating colours leads to the red-green-red-green pentagon diagram shown earlier in the thread. This can’t be coloured correctly.

With a little more work these might be avoided and then it might be possible to create a tiling.

2. Tom Sirgedas says:

Gotcha! Here’s another attempt, with computer help.

3. Tom Sirgedas says:

Oops, sorry, I just realized I broke the same rule again!

16. ag24ag24 says:

It would also make me much more comfortable if I felt I really understood the difference between “measurable” and “tile-based”. Townsend and Coulson provided proofs of a lower bound of 6 for tile-based colourings, and their definitions of “tile-based” seem to me to be the same, but I am acutely aware that I may be missing something, because for the life of me I cannot get to the bottom of why Falconer’s proof of a lower bound of 5 doesn’t already cover the same set of colourings. I know Bernhard is offering his own route to this, but my question is purely with regard to definitions. Can someone please give me an example of a colouring (of whatever chromatic number) that is measurable but not tile-based and that cannot trivially be converted to one of the same chromatic number that is tile-based?

1. I would also like to have a better understanding of the difference of the measurable and tile-based cases, but I did have my interpretations of how this might work. So far I thought that the measurable non-tile based constructions may refer to things such as the Smith–Volterra–Cantor set, or in general fractals with a fitting measure.
Specifically it should be possible to put the SVC in a [0,1) interval and assign color 1 to it, yielding a measurable distribution of both colors, even though color 1 is nowhere dense, and thus not a real tiling. In this case we do still have discernable tiles of color 2, but we can get rid of these as well if we want to.
But I don’t know if that’s what’s being speculated about, nor do I know any way to properly generalize such attempts into 2 or more dimensions.

2. @ag24ag24 Why is measurable important in your question? I thought that we simply do not know any colorings that cannot be converted into tile-based colorings. The problem is, that we cannot prove that they can be converted, no?

1. ag24ag24 says:

Domotor – thanks – I think the answer to your question is that I understand even less about my question than you think I do! My question is really independent of colourings, or at least independent of chromatic number. My request is simply for an example of a division of the plane into a finite number of sets, each of which is measurable, and yet which does not entirely consist either of tiles of radius at least some x or of regions that can harmlessly be replaced by a tile of radius at least x. Bernhard’s mention of (the 2D equivalent of) Cantor-family sets is a start, but I don’t see how such a partitioning can be constructed so as to avoid the ability to merge any connected set of regions smaller than some finite radius into one region without increasing the chromatic number. I’m assuming that such a partitioning of a sufficently large finite region of the plane consists of an infinite number of tiles each of finite (but with no minimum) area – right? Where I’m hanging up is that the proportion of the plane occupied by connected sets of regions of radius at most x tends (?) to zero as x does, hence surely we necessarily end up in a situation where these regions are separated by distances that exclude 1. What kind of partitioning of the plane doesn’t yield to this sort of transformation?

2. I don’t think I can follow your reasoning. Would it also work in 1-dimension? How would you convert an arbitrary 2-coloring of $\mathbb R$ into a tile-based coloring?

3. I’ve had trouble following it too. Maybe some more elaborations would help.

@domotorp: There’s a big issue with considering a unit distance graph defined on $\mathbb{R}^1$, which is that this graph $G_1$ is disconnected. There’s no path from 0 to 0.5 or to $\pi$ and so on. This means we can color an initial interval like [0,1) basically enitrely randomly, so long as we then color the rest of $G_1$ accordingly. It is sufficient to consider the coloring of the actual graph components, $\mathbb{Z}$ sets, because no color restrictions can go beyond the integer set they’re contained in. So the considerations for 1 dimension, or more than 2 dimensions change drastically due to connectedness.
In fact I don’t know of any, and can’t imagine any infinite graph defined on $\mathbb{R}^1$ which is fully connected, unless this connection implies intervals, and thus tiles directly.

But since you brought it up I’ve also been meaning to ask, what exactly do we define as a valid conversion in the first place? Clearly in $G_1$ we can just slap a fitting tile into it, anywhere, and propagate the changes through the rest of the graph, replacing the original coloring, whatever it was. We can also take any nowhere dense set and make it dense in a fitting interval, and again propagate the according changes. In this manner I can contrive basically an infinite amount of things I’d consider valid conversions.

But what would we consider a valid conversion for $G_n$ with n being 2 or higher, and what not?

4. ag24ag24 says:

@domotorp – I wasn’t claiming that arbitrary colourings can be converted to tile-based ones, only that Cantor-like ones can. I define these to be more general than tile-like colourings only in that tiles can be arbitrarily small, thus allowing infinitely many tiles in a finite area, whereas the colourings proven by Townsend and Coulson to require six colours implicitly possess a minimum area for a tile (don’t they?). But I could be wrong even about that… Beyond that, I’m still hazy as to what “measurable” really means, but I’m guessing that it is considerably more general than Cantor-like – including, for example, disconnected regions consisting of a tile and a point.

Basically my interest in these definitions is because I am thinking that there may be value in defining a hierarchy of classes of colouring, more finely-grained than just arbitrary vs measurable vs tile-based vs scaleably tile-based, so as to give more options for proving bounds on particular classes and thereby inching our way towards an exact value for the CNP. As things stand, measurabiity has indeed lost its earlier relevance, because we now have a lower bound of 5 unconditionally – but one can very much imagine a future in which Falconer’s method is strengthened to give a lower bound of 6 and Townsend’s is strengthened to 7 – and one can similarly imagine the demonstration of lower bounds of 6 or 7 for criteria other than measurability and tileness.

5. Sorry, what I meant to ask was how would you convert a “Cantor-like” coloring to a tile-based one in $\mathbb R$? While I know the definition of measurable, I struggle to grasp what “Cantor-like” exactly means. Btw, if you’re looking for intermediate types of colorings, there is the Borel hierarchy. What can we say about colorings when every color class is Borel, or is on some fixed level of the Borel hierarchy?

6. And let me add that I’m not particularly interested in such questions, I just wanted to offer an intermediate option that you’ve asked for.

7. ag24ag24 says:

Many thanks Domotor – very useful (whether or not you are interested :-)). I gave my definition of “Cantor-like” earlier – it surely has an existing name that I don’t know – I just mean partitions of R^n in which every point is within a monochromatic region of non-zero width. It seems to me that Townsend’s proof can’t work when “tiles” can be arbitrarily small. Thus, I was saying that surely any partitioning of the plane in which tiles CAN be arbitrarily small can be converted harmlessly (i.e. without increasing the CN) into one where they can’t. However, I’m now seeing my error: I was thinking that if the regions occupied by really small tiles are really small, then they must eventually (for suffciently small “small”) exclude a distance. But now I’m realising that these regions will also be increasingly finely scattered, so that that isn’t necessarily true. Apologies. I will now go look up the Borel hierarchy!

8. I was wondering if it was the fine dispersal you missed. I had mentioned this effect, albeit in a completely different context. It’s also one of these deceptive traits of the problem that makes it look like there should be relatively easy way there to prove the need of n-dimensional regions for $\mathbb{R}^n$, but I just used up like 2 months looking for this way without success. I still think it exists but I sure won’t be trying again, the measure based approaches tend to be very complicated.

17. Michael Ruxton says:

An example of a partition of the plane into “measurable” sets which aren’t simply-connected tiles. Use the hexagon tiling which seven-colours the plane. Now our sets aren’t individual hexagons but a cluster of three nearby hexagons, all clusters with the same orientation, each hexagon in a cluster with the same colour. Maybe Aubrey is asking for something more complex than this.

1. I may be missing something but I don’t see how this would work out. If I can describe any of the hexagons with a Jordan curve than I can view that as a tile, or very trivially convert it to a simply connected tile. Can you provide a picture or some more specific math of what you mean?

18. Michael Ruxton says:

Sets G2,R2,P2,T2,O2,Y2,B2 are each translates of G1,R1,P1,T1,O1,Y1, and B1, and so on. So our eyes see hexagons, but our sets are defined by groups of three hexagons of a given colour.

1. I think I get what you mean now, essentially you suggest imposing additional structure by grouping things up in such a way that the groups themself aren’t continuous tiles, even though the individual tiles in that group are.

I don’t think that’s a valid approach though, as it requires adapting the entire question to fit these groups. The type of coloring we’re looking for is one that can’t be split into tiles in any way, such as the nowhere dense fat Cantor sets. The hexagons above, grouped or not, have dense areas and Jordan curves which are essentially tiles.

19. Sorry I haven’t checked in for a while, I was busy with several other things (including a trip to Bristol). I’ve been playing around with seeing what one can say about colorings of $R_2$ by human means, as discussed by Phillip. I found it convenient to normalise the coloring by identifying the four colors with the finite field $R_1/2R_1$, and then subtracting off a copy of the projection map from $R_1$ to $R_1/2R_1$ for any coset of $R_1$, because the monochromatic components of the resulting difference have a nice structure (they are all “convex” subsets of the coset). I wrote up what I managed to obtain at http://michaelnielsen.org/polymath1/index.php?title=Coloring_R_2 . The best result I have is Corollary 9, which asserts that if the coloring is $2R_1$-periodic on $R_1$, then this periodicity automatically extends to the larger lattice $R_1 + \eta^2 R_1$. where $\eta = \exp( \frac{i}{2} \arccos \frac{5}{6} )$. This sounds like enough structure that one could then classify the rest of the coloring on $R_2$, but I was not able to finish this off yet, and also I would of course like to remove the initial hypothesis of periodicity on $R_1$.

1. Philip Gibbs says:

This is excellent. I have to come back to looking at 4-colourings of $R_2$ soon.

20. I’ve got another result that puts further constraints on possible efficient colorings of the plane and higher dimensions, this ones about the shape of the boundaries. Like I had previously conjectured we’re not just forced into using Jordan-Brouwer separated spaces, that is Jordan curve bounded regions in the plane (tiles), but there’s a tangible constraint on the shape of these regions as well. It’s easier to find and prove than I initially thought.

The curvature of the boundary is limited to arcs with radius of unit distance or greater, because every arc with a radius that’s smaller than 1 can be filled up to radius 1 without increasing the exclusion zone. This can be shown even without an actual tile, two perpendicular lines are sufficient.

I’ll be adding this in a formalized way to my paper eventually.

1. I do not think such a coloring can exist, and the contradiction I’m working on, indicated in the post below, would be the proof for that.

It requires a tiling that is scaled down enough that there are 2 layers around a cell that aren’t within its exclusion zone yet, so that our base cell can be red as well as a cell in the second layer around it, leaving the first layer to break the color connectedness.
I’ve looked into such constructions a couple of times before and so far their chromatic colors were all clearly beyond 7.

By tapping into scalability of some constructions we can put some misplaced vertices/lines into them to satisfy the indicated conditions… but doing so clearly yields a situation that can just as trivially be reversed.

I’m curious what you’re getting at though.

2. ag24ag24 says:

@domotorp – yes, it’s not at all easy. I am not sure about Bernhard’s argument, because I think it is evaded by variations on the Pritikin construction. Recall that we can eliminate a single small tile from Pritikin’s tiling by fattening the opposite edge of each of the four heptagons (now hexagons) that surround it, and adjusting lengths (including somewhat enlarging some other small tiles). We would thus have what you request if we could do this for alternate pairs of small tiles (i.e. for the nth tile in a column wherever n mod 4 is 0 or 1), since adjacent pairs are less than 1 apart but pairs three apart are more than 1 apart (as are pairs in separate columns). Unfortunately, though, the fattenings from neighbouring columns can’t quite be made to interlock compatibly. I haven’t yet convinced myself that similar tweaks to that tiling (involving, for example, eliminating only parts of certain small tiles) can’t work, though.

1. I’ve taken a brief look at this and still can’t see it work either, yet. If it does actually work however it’d be great to find it and understand why it can work. Because if it’s so then I might have two stages of generalization in front of me, not just one.

Of course, if we grant the ignoring of some tiles then we can even use the original Pritikin tiling to satisfy these conditions. I see no use in doing so, but I feel there’s probably something about the question here I’m missing anyways.

2. ag24ag24 says:

Right. And actually, constructions of this form don’t really satisfy Domotor’s request anyway, because (even in Pritikin’s original) we can add a stripe of colour 0 between any adjacent pair of small tiles, which I think counts as trivial. What we really need is a 7-colouring in which one colour consists of small tiles at the vertices of a (most likely triangular) grid of edge-size less than 1.

3. ag24ag24 says:

Ah. Can’t we do it just by stretching Pritikin’s tiling vertically a bit? If the large tiles are made to be of height 0.6 rather than 0.5, the small tiles can all stay, and we definitely can’t join any pair of them with a stripe of colour 0. We need to enlarge them a bit, sure, but surely not so much as to break the colouring – right?

4. Hm, if we consider such stripes then not even my suggested construction, which I already consider to be impossible, would be enough. We would need really small tiles, so that another exclusion zone for a given color is able to pass between two tiles of that color without touching either of the tiles. So we probably need more like 2 and a half untouched inner layers or more.

5. “Can’t we do it just by stretching Pritikin’s tiling vertically a bit? If the large tiles are made to be of height 0.6”
Not quite… but I got what you’re getting at and actually you’re right, I managed to construct that thing you likely thought of.

The exact construction is like this however: Scale the entire Pritikin tesselation up vertically by $\frac{4}{3}$, so the diamonds have a height of $\frac{1}{3}$ (and the heptagons $\frac{2}{3}$, ), then scale it down horizontally until the heptagons do not intersect their own exclusion zone anymore (0.87 or something). And that’s pretty much it, now we have a 7-chromatic tesselation with one type of tile, the diamonds, satisfying the requested conditions.
It does however rely on tiles of heavily different diameters, I still think that this isn’t going to work with tesselations using tiles of same/similar diameter.

@Domotorp: Here’s a picture of the tesselation and the diamonds, which should fulfill your requirements:

1. Yeah, this indeed seems to be just what I was looking for, thanks!

2. Glad to hear that and you’re welcome. Looking forward to seeing what you can do with it, I still can’t even imagine what its purpose is.

3. ag24ag24 says:

Thanks Bernhard. Actually Pritikin’s diamonds are far smaller than the ones you used (they are very much not to scale in his figure 3) – but as you say and show, diamonds as large as a height of 1/3 still work.

Domotor – I’m guessing that your question was motivated by the idea that if it is really hard to do this with seven colours then maybe we can come up with a proof that it is impossible with six colours, which would greatly simplify Philip’s strategy. I think there is still mileage in that concept. As Bernhard notes, there are probably some quite broad criteria that one can demonstrate to be incompatible with your request. Conversely, of course if a six-colour solution DOES exist that has some small tiles, maybe a way to cut through the complexity of enumerating options is to focus on tilings that are in some sense similar to 7-chromatic solutions.

4. ag24ag24 says:

Indeed, just yesterday I was musing as follows:

The set of points at unit distance from some point in a tile T of diameter less than 1 forms an annulus-like shape around T. Let’s call it the annulus of exclusion of T, AE_T. Like any annulus it has an interior and an exterior.

Suppose a tile-based colouring exists that contains two tiles A and B, both colour 1 and lying entirely within the interior of each other’s AE. Let’s wlog assume that there does not exist a curve joining the two tiles and lying within the intersection of the interiors of AE_A and AE_B but avoiding all exclusion zones of other tiles of colour 1, since if such a curve exists we can make it the same colour as A and B, causing A and B to cease to be distinct tiles. This can occur in two topologically distinct ways:

1) A third small tile C lies nearby, such that (wlog) A lies entirely within the interior of AE_C and B lies entirely within the exterior of AE_C..

2) Two (not necessarily small) tiles C and D exist that are just slightly more than 1 from A and B and slightly less than 2 from each other, such that AE_C and AE_D intersect between A and B but both A and B lie entirely within the exteriors of AE_C and AE_D.

Case 2 is pretty damned restrictive. Can we eliminate it? Case 1 is much less restrictive – in particular there could be more than one “third small tile” – and as we have now seen, it can indeed be achieved if we allow seven colours.

5. The “purpose” of my question was to see which direction to go on. In case of a negative answer, it would have restricted tile-based colorings even further. But the answer is positive, so I guess this gives a sliver of hope to find a 6-coloring.

Cases 1 and 2 that Aubrey mentioned are interesting variants that I didn’t think of beforehand. Bernhard’s construction is Type 1, so the existence of a Type 2 construction is still open then.

6. ag24ag24 says:

RIght. It might be profitable to deform the Pritikin structure a bit more, in fact – specifically, to make the diamonds cover as much as possible of the plane rather than as little as possible. Their vertical dimension is already maximal at 1/3, but they can be extended horizontally to comprise the entire intersection of unit-diameter circles with centres 2/3 apart, and then of course the columns can be brought closer together. What is the resulting maximum proportion of the plane thus covered? What are some promising options for partitioning the rest of the plane with five colours?

7. Further expanding the diamonds gives us a lot of choices to go into, not just straight up making them larger and pulling them together, but also interleaving them with tiles of other color but the same shape. We probably have to do the latter to maximize the proportion covered.

The thing I don’t see working is trying to create a tiling where, ignoring the diamonds, no 6 tiles are in reach of one another. If 6 tiles are in reach of one another they form a complete contracted graph and all of them will be touched by the diamond exclusion zones, bringing us to 7 colors.
If there’s a 6-coloring then the simply shifted column structure likely isn’t going to get us there. Within a column a tile definitely forms a complete graph with the tiles above and below, bringing us to a 3-complete segment within a column. We should be able to use the diamonds in such a fashion that we only need to consider one more adjacent column. In the original Pritikin tesselation every heptagon reaches 6/5 heptagons in the adjacent columns.
Bringing this down completely to 5 is certainly doable, maybe even 4… but we need to crack it all the way down to 2 to avoid a 6-complete tiling, otherwise we will have 3 on one, and 3 on the other side, all in reach of one another.
That’s very, very far away from what seems doable to me.

Maybe there’s another structure that makes better use of the diamonds? I’m unable to think of anything however.

21. @Philip: Posting this separately to keep things more ordered.
It’s certainly a good start and gave me some ideas to work with.
“This means that the cells must either be small enough to allow surrounding cells to fit within a diameter of one, or the cells themselves must all have a diameter of exactly one.”
Right, this is perfectly in line with my observation of dual tesselations, it leads to a very condensed result on the chromatic number of tilings under specific circumstances, the layers touched by an exclusion zone.
1st layer: All cells adjacent to our base cell
2nd layer: All cells outwardly adjacent to cells in the 1st layer
3rd layer: All cells outwardly adjacent to cells in the 2nd layer

If a tiling has the first 2 layers in it’s exclusion zone, then every cell will form a contracted complete graph with all tiles at distance 0, or with the first layer around it.
So clearly for a hexagon grid we have the 7-complete contracted graphs, as it is scalable either way. A normal square grid has 9-complete contracted graphs, the pentagon tiling 8-complete and so on. The bitruncated cubic honeycomb in 3 dimensions works in the same way and builds 15-complete subgraphs. The reason it is unscalable is because the exclusion zone is at distance 0 to cells in a third layer, so any scaling causes the exclusion zone to start reaching into the third layer. It seems likely that in higher dimensions we’ll have to reach into deeper layers, but not yet in 3 dimensions I think.

What we essentially do with the diameter 1 constructions is partially break connection to the second layer, which in most cases will yield a better chromatic number, but can never worsen it.

So this is why a bit of scaling down cannot ever help us. We need to scale down a lot before the 1st layer leaves the exclusion zone, and we will always reach more cells in the other layers first. As we scale down we also will not ever encounter large complete contracted subgraphs again, as for these complete subgraphs we need the inner layers. That means the higher chromatic color comes from critical subgraphs in the contracted graphs as we scale down, and they can reach way past 7 and so on because the contracted graph isn’t unit distance.

I now think there should be a way to generalize my math on the dimensional escalation yet a bit further. It forces near vertices into tiles, otherwise the chromatic number may rise, which so far told us that a coloring of higher dimensional euclidean spaces strictly relies on cells even without artificial constraints.

If we have a tesselation that’s scaled down enough, so that the first layer leaves the exclusion zone, we can assign two adjacent tiles the same color, which would essentially fuse them back into one tile. I’m very sure that by the same token dimensional escalation will force near tiles into the same color, if possible. Given that I already rather thoroughly formalized the dimensional escalation process this looks like a very promising approach, and shouldn’t be too hard to put into new testable math. I’ve definitely got some ideas to test, maybe I’ll even find some simple but solid contradiction as with the case of n-ball expanded graphs. We’ll see.

“Unless they made extra assumptions their argument must apply to small cells.”
Right, Coulson explicitly stated in his paper:
“…polygonal tiles (all with area greater than some positive constant)”
But small cells are still possible, unless we find the necessary contradiction.

“This should provide a set of single tile pieces that can then be fitted together like a jigsaw puzzle, perhaps.”
That’d be super neat. Looking forward to seeing if that works out. Even if there’s no reasonable small cell jigsaw puzzle, there might be one with preset lines/arcs of certain lengths from which we can make valid cells.

22. Philip Gibbs says:

Here are the combinations for single tiles modulo symmetries with different vertex valencies. Unit length constraints are shown. Edges shown as straight lines may be curved. Hope I didn’t miss any.

Many of these are unlikely candidates. The angles at vertices are frequently constrained to be quite large.

The next step might be to look at all ways of fitting four tiles round a vertex of valency four. I am not sure if there might be too many options.