Polymath16, eighth thread: More upper bounds

This is the eighth “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:

– We can now 4-color the disk of radius 0.869, 5-color the disk of radius 1.1, and 6-color the disk of radius 1.85, though it appears that a larger disk is 6-colorable.

– We now have a human proof that p_d<0.49 for d \geq 0.52.

There is ongoing work to improve Thomassen’s result so that the tiles need not be strictly smaller than 1 nor have distance strictly larger than 1. This would produce new obstructions to 6-coloring the plane.

Advertisements

121 thoughts on “Polymath16, eighth thread: More upper bounds

  1. I have tried Philip Gibbs’s approach to finding pentagonal tilings, as in this comment here: https://dustingmixon.wordpress.com/2018/05/29/polymath16-sixth-thread-wrestling-with-infinite-graphs/#comment-4722

    Specifically, I translated the problem to a SAT instance and then just ran minisat. If my results are correct, then it is possible to color a 6×10 grid

    but it is not possible to color any larger grid (ie, neither 6×11 nor 7×7).

    I haven’t tried extracting interesting insights from these constructions. Maybe there are portions of this grid that can be extended in a way that is incompatible with coming from a hexagonal grid.

    1. Nice! It seems to have complete rotational symmetry except for one edge at the sharp corners. I wonder what it looks like geometrically, and also what configuration of Philip’s 18 tiles it uses.

      It might be interesting to find the smallest grid (in terms of number of verticces) that can’t be done. As a start, try a hexagon of edge 4?

      1. Thanks! So the addition of 12 vertices to that, six at top left and six at bottom right, is not possible. I guess it should be pretty easy to interpolate and find the minimum impossible shape, but maybe that’s not very interesting.

        What may be more interesting is to see whether the largest solutions are geometrically realisable. I note that 37 (let alone 60) is quite a bit larger than the most tiles that Philip or I have succeeded in putting together 6-colorably. Has anyone managed to find a tiling corresponding to Boris’s grids, or indeed anything over 30 tiles? And for that matter – Boris, were you able to solve a 5xN parallelogram for arbitrary N? – that’s more than the four that we’ve realised in a tiling so far. I’m thinking that we’d actually hope that the attempt to create tilings that correspond to SAT solutions fails, because then it may reveal additional constraints (over and above the convexity conflict that Boris already incorporated) that would narrow the search for how to combine Philip’s 18 tiles.

      2. Unfortunately when we try and map these to a geometric tiling we find new constraints. For example in the tile below the configuration of the colours 0,5,4,0,5 along the yellow line around the two diamonds forces constraints on the central tile that would give it a diameter greater than one (all the pink lines have to be length one) It might be possible to add this new constraint and others into the SAT solver until we actually get something that works, but possibly hard work.

      3. The strip one is more interesting. I already looked at something like it and I think it can be made into an interesting geometric solution. I will try and draw up what that looks like.

      4. Here is what you get if you turn the strip into a geometric tiling. It does not set any records but at least it shows that some of these patterns do work out.

      5. Correction. The colours need to be shifted like this.
        By the way a complete 7-colouring is possible if the strip is extended outwards.

      6. @Philip – I don’t agree at all! That (i.e. the identification of a new configuration in the triangular grid that is geometrically prohibited) is the answer I was hoping for, and I think it is mighty interesting and promising – precisely because it (perhaps after we find a few more of the same) will allow your search for admissible combinations of your 18 tiles to be streamlined, hopefully to the point of tractability. Won’t it? – am I missing something?

        Of course many other steps also remain to be attacked. The first, I guess, is whether there are pentagonal tilings that are not represented by an edge-depleted triangular grid. Do we yet have a sense of whether there are, and if so how to generalise that grid to include such, so that the SAT approach can be applied?

      7. I’d also say the identification of these configurations, step by step, will eventually get us further. One very prominent feature all of these 6-chromatic tilings so far have is that the only work of they’re ‘centered’ around a point or an axis, and then only to some radius. I still don’t know what math is happening there, but once we do it’d help open up a different type of path to fundamental condition proofs than those I’m working at.

      8. I feel a little like Buridan’s ass here. Do we go for the full computational approach to search systematically over all possible solutions, or is it worth spending more time to understand the theory of the constraints first?

        On the theory side you can look at subgraphs formed by joining up vertices with valency of four or higher. Constraint lines radiate out from these networks. Are there counting arguments that determine impossibility?

        For the tiles, first a little good news: tiles L, D, G and H can be taken off the list because the blue tile is joined by an edge to two tiles of the same colour, so there are 14 pentagonal tiles left (see end of sixth thread). I should have spotted that earlier. The strip above uses tiles K and W. It is worth seeing how close this tiling comes to failing in different ways. The K tiles have two diagonals of length one in addition to the two forced by the constraints. They also have a width of 0.5 so that K-tiles of the same colour separated by two of these are only just safe. It is only the sequence of W tiles that stops it working further.

        The grid structure only includes pentagonal tiles where 1, 2 or 3 vertices have valency four. It therefore does not allow for tiles M, F and R. Perhaps there are others from this list that are excluded

        I started to look at a more full list of tiles allowing triangles and squares and valencies up to six. I had to resort to the computer even just for this. I will try and complete that.

        For a full search of possible tilings there is no easy option. You need an algorithm that can systematically build general planar graphs and then try to colour them.

      9. Many thanks Philip. Wow, I too should have spotted the problem with those four tiles. Sorry!

        Yeah, it’s a dilemma – but I think the approach we’re gravitating to is kinda a resolution of it, in the sense that we are nibbling bits off both the theory and the computation that each potentially render the other more tractable. In particular, if you think you may be within computational reach of a full enumeration for tilings in which no two tiles lie inside each other’s annulus of exclusion, that gives us a lot of motivation to try to exclude such tilings by theory.

        After we solved Domotor’s challenge to find a non-trivial example of such a tiling that was 7-colorable, I played around a bit trying to find other examples and tentatively concluded that we can place quite a tight upper bound on the size of such tiles, and that those bounds get steeply tighter as we move to more complex configurations of such tiles. Therefore, maybe there is mileage in returning to the question Dustin and Hans explored way back, of the 6-colour version of the Pritikin tiling. We don’t have a proof (do we?) that Croft’s tiling minimises the area occupied by the wildcard colour in a (4+wild)-colouring, but that feels awfully within reach – and maybe if we had such a proof we would see a way to extend it to the 5+wild case. If we obtained a proof that the wildcard colour must cover at least (say) 3% of the plane, I think we’d have a good shot at identifying all the possible small-tile topologies that remained to be eliminated more laboriously. (Then again, if we got THAT far, maybe we could take the analogous step and get a positive lower bound on the 6+wild case…)

      10. > and valencies up to six

        Actually, you can show that no tile can be adjacent to 6 other tiles in a 6-coloring. Suppose (to the contrary) that a tile T is adjacent to 6 other tiles. Then by pigeonhole, two of these adjacent tiles, call them A and B, receive the same color. Pick \epsilon\in(0,1) small enough so that we may select \epsilon-close points x_1 and x_2 in the boundary between A and T and similarly \epsilon-close y_1 and y_2 in the boundary between B and T. Then the distance between x_i and y_j equals 1 for every choice of i and j. That is, the points x_1,y_1,x_2,y_2 form the vertices of a rhombus with unit side length, meaning either x_1 and x_2 are at least \sqrt{2} apart or y_1 and y_2 are. This violates the fact that \epsilon<1.

      11. @Dustin: I believe that the valencies Philip was referring to were those of the vertices of the actual tiling (i.e. the graph consisting of the boundaries between tiles), not of the dual graph. Clearly the valency of vertices in a k-colour tiling can’t go above k, but I don’t see an obvious way to exclude k.

        Also, regarding your argument (which addresses the valency of the vertices of the dual graph), the issue is that with small tiles that lie within each other’s annulus of exclusion it is no longer true that x_i and y_j are 1 apart. My solution to Domotor’s challenge shows this – it is a 7-tiling that involves heptagons.

      12. Er, I wrote: “Clearly the valency of vertices in a k-colour tiling can’t go above k”. Clearly that is not clear at all, since two tiles of the same colour can happily coexist at a shared vertex if they both lie entirely within each other’s AE, which in this case just means lying within a particular Reuleaux triangle that has a corner at that vertex. But I think we can exclude that situation, because I can’t think of a way to stop such a tiling from being transformed harmlessly into one in which the intersection of that Reuleaux triangle and a (sufficiently) small disk centred on the vertex in question is changed to the colour in question.

      13. I wrote: “I don’t see an obvious way to exclude [a valency of k in a k-tiling].”

        But actually…

        Suppose that a 6-tiling has a 6-valent vertex V, and further suppose that we have done the transformation I just described, so that no two tiles with a vertex at V are the same colour. Then all six colours are present in the immediate neighbourhood of V. Thus, unless I’m missing something really obvious, those six tiles must jointly cover a disk of radius 1 centred on V, and the boundaries between them must meet the edge of that disk at the vertices of a regular hexagon. Thus, each tile must lie entirely within the Reuleaux triangle defined by its vertices. Now consider the tiles adjacent to this disk – what are the options? I’m not seeing a quick way to entirely sidestep the style of analysis that Philip has been pursuing with his gang-of-14, but I’m betting that it can be somewhat streamlined by appealing to the above. In particular I think that most of the points at distance 1+epsilon from V will have only two colours available, with the details depending on how the tile boundaries emanate from V.

      14. I looked at the six valence case like that too. I also concluded that you get a circle divided into six tiles around the vertex and meeting at a hexagon, but what next? You can arrange the next layer of tiles with one, two or three joining per sector and have to look at each case separately. I don’t think any options work out very far but unless there is a missing trick it requires exploring all the cases systematically.

      15. Yeah, I agree, I don’t see a magic next step. However, with so much symmetry being present, it seems to me that there is likely to be a human-manageable number of individual cases.

    2. Very good. The biggest I reached was 6 by 7 and it is good to confirm that there is indeed an upper limit.

      I looked at trying to code up a more general search allowing for higher valencies and tiles with fewer sides, but it is a major task.

      it does seem that whatever you try the tiling gets stuck beyond a certain size. It is difficult to see if there is a simple principle at work or if it can only be verified by searching through cases.

  2. Might it be useful to try to identify example colourings that distinguish the various criteria for which we have lower bounds? For example, we know that scaleability distinguishes the Townsend criterion from the Thomassen criteron. I think I’m right in saying that a colouring which distinguishes Philip’s recent path-based one from Townsend’s one would be two tiles joined by a path of zero width. I’m also still curious as to whether Falconer’s result applies to, for example, colourings in which each colour includes tiles and also regions of measure zero (such as isolated points), Then there’s what I earlier termed “Cantor-like” colourings in which all regions are tiles but with no minimum area. And so on. I’m thinking that the identification of such examples might productively guide the search for strengthenings of the various proofs. Can we make such a list?

  3. Here’s where I am with the fundamental conditions for receiving chromatic colorings.
    For every infinite graph that can be described with a consistent exclusion zone and the space on which it is defined there exist paradigms (for lack of a better word or knowing already existing notation), yielding various valid colorings. A paradigm is efficient for a graph if it yields a coloring with the actual chromatic color of the graph, otherwise it is inefficient (or even invalid).

    Just as we can generalize exclusion zone definitions to span a class of infinite graphs rather than one in particular, we can create generalized coloring paradigms spanning such classes.
    A hexagon lattice-sublattice scheme would be a coloring paradigm for the plane.
    A permutahedra lattice-sublattice scheme wold be a valid coloring paradigm for any dimensionality. Such a generalized paradigm is optimal if it yields the chromatic number for any possible case for the class of graphs it is used on. In other words, such a generalized coloring paradigm would allow us to compute \gamma(G_n) for unit distance graphs defined on \mathbb{E}^n. Finding, understanding and proving such a paradigm would be pretty much the complete solution to the Hadwiger-Nelson problem, but achieving this is clearly highly unlikely.

    In our case it means that an optimal coloring paradigm has to be built upon conditions that seemlessly translate into all dimenionalities. As such, if we can prove that condition x becomes necessary for chromatic colorings in dimensionality 2 and onward, we’d expect to fo find some efficient coloring paradigms for dimensionality 1 obeying the condition and yielding a chromatic color, even though it’s not yet required for chromatic colorings.

    We know that coloring euclidean unit distance graphs requires Jordan-Brouwer separated spaces for dimensionality 2 and onward, but the same does generalize to dimensionality 1 as well, with intervals such as [0,1). This automatically implies measurability as well.
    (It generalizes to 0-dimensionality with some rephrasing as well, but we’ll ignore that for brevity’s sake. There is also a superclass of infinite graphs, containing euclidean unit distance graphs, which requires an optimal coloring paradigm to use sets that are locally homeomorphic to their containing graph component.)

    We define the boolean function cc which tests whether 2 points are color connected, or in other words joined by a monochromatic path.
    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}f(j)\biggr)=1

    Using this function we can easily define an equivalence relation. We know that an optimal coloring paradigm requires the set of all [a]Rcc to contain some JB separated spaces with the according dimensionality, and there’s definitely an optimal coloring paradigm where [a]Rcc exclusively contains such spaces, essentially making [a]Rcc a graph filling set of tiles.

    Now on to some conjectured conditions:
    For an optimal coloring paradigm the set of all [a]Rcc…
    …has to contain some tiles which have some vertex on their boundary whose exclusion zone comes arbitrarily close to another vertex in the same tile. Or simpler, partially bounded diameter 1 tiles.
    I deem this to be extremely likely and I’m still looking for a tangible proof of this.

    …has to contain exclusively partially bounded diameter 1 tiles.
    I deem this possible, but a proof or refutation of this condition likely has to happen in 3 or higher dimensions. I wouldn’t bet on it though.

    …has to contain some tiles with a simply connected, (n-1)-dimensional subset of vertices on the boundary whose individual exclusion zones all come arbitrarily close to another vertex in the same tile. Or more simply, that’d be the arc curves we see in the constructions discussed and presented by Aubrey and Philip.
    By now I do deem this pretty likely as well. A proof of this would no doubt be another big breakthrough, and finding a 6-coloring of the plane with the current discussed techniques would be pretty much an instant proof. It might however be necessary to go up to 3 dimensions to proof or refute this. Clearly this condition contains the partially bounded diameter 1 condition, and that’s why I’m also looking for a proof of this on the side.

    …has to contain exclusively arc curve boundaries.
    I guess there’s a slim chance for this but I severely doubt it. Just having it here for the sake of completeness.

    I had to get this out to restructure my thought process on this.
    My main question to others is, do we have any other conjectures or proven conditions except the ones I mentioned?

  4. Domotor and Terry: do we have sufficient closure on your discussion of upper bounds on p_d for sufficiently large d that we can update the table on the wiki? It’s a bit of a mess right now with a sprinkling of 94’s and 188’s and nothing better – and no mention of the improvement to 0.48 even in the text of Prop 36 (should that be a separate proposition?).

  5. I’ve been thinking about how we represent the tiling problem in terms of coloring dual graphs. At the moment, I’m aware of two non-trivial constraints, depicted in the following comments:

    [1] https://dustingmixon.wordpress.com/2018/05/29/polymath16-sixth-thread-wrestling-with-infinite-graphs/#comment-4690

    [2] https://dustingmixon.wordpress.com/2018/06/24/polymath16-eighth-thread-more-upper-bounds/#comment-4934

    In both cases, the constraints result from contradictory requirements on the shape of a vertex’s tile. Presumably, all of the constraints (even the ones we haven’t observed yet) boil down contradictory shape requirements. This suggests that we try to understand what sorts of shapes are possible. Indeed, Philip has made several strides on this end; see for example:

    https://dustingmixon.wordpress.com/2018/05/29/polymath16-sixth-thread-wrestling-with-infinite-graphs/#comment-4789

    I wanted to point out a nice way to encode shapes that might suffice for our purposes. Given a proper 6-coloring of a dual graph, label edges in the graph according to the following rule: If a vertex u is adjacent to a vertex v of color c, and u also shares a face with another vertex w of the same color c, then label the edge {u,v} with w. For example, here’s a representation of Philip’s tile A:

    Intuitively, the edge labels indicate how tiles should “balloon out” (namely, toward the vertex with the same color as the vertex named in the edge label). It appears that the existing constraints can be expressed in terms of this representation. In particular, as a generalization of [1], I think it should be a constraint that no edge receives multiple labels.

    1. Yes this is a useful way to classify the tiles and combinations of tiles to systematically explore the possibilities.

      1. Regarding Buridan’s ass, I chatted with Boris, and we agree that it would be best to first identify all “feasible neighborhood colorings.” Specifically, we want to know all ways to color 3-, 4- and 5-sided tiles along with their neighborhoods, generalizing your partial classification here:

        https://dustingmixon.wordpress.com/2018/05/29/polymath16-sixth-thread-wrestling-with-infinite-graphs/#comment-4789

        For example, constraint [2] above boils down to whether a neighborhood coloring is feasible, whereas constraint [1] above is more of a consistency constraint between overlapping neighborhoods (which can be encoded using edge labels). Ideally, this classification will be computer-readable. Once we have this, then we can systematically build up colored plane graphs that satisfy both types of constraints.

      2. I’ve been trying this too. It seems unfortunate that cases (1) and (2) above should be so distinct; is there a generalisation? My best idea so far is to identify satisfiability constraints on small graphs whose vertices are the vertices and edge-midpoints of the tiling. Thus, (1) can be stated as the fact that no five points A,B,C,D,E can have AC=AD=AE=BC=BD=BE, and (2) can be stated as the fact that no four points A,B,C,D can have AC=AD=BC=BD>=AB>=CD. (In the former case, E is the midpoint of CD; in both cases A,B,C and D are vertices of the tiling.) Can we come up with a provably sufficient list of such constraints?

      3. Here’s a stab at classifying all feasible neighborhood colorings of 3-sided tiles.

        First, we need some notation for neighborhood colorings. Consider the following encoding of the neighborhood coloring of Philip’s A tile above:

        yellow, (purple), green, (), blue, (yellow), purple, (), brown, ()

        Here, we alternate between an edge color and a (possibly empty) list of vertex colors. Note that the overall neighborhood color sequence exhibits “wrap-around,” so that the first edge color is “after” the last list of vertex colors. What follows are some defining characteristics of neighborhood color sequences:

        (N1) All of the colors are drawn from a common set of 5 colors.

        (N2) Every edge color differs from the preceding and following edge colors.

        (N3) All of the vertex colors in a common list are distinct.

        (N4) Every vertex color differs from the preceding and following edge colors.

        Note that (N1)-(N4) together imply that each list of vertex colors has length at most 3. Since a 3-sided tile can take the shape of a Reuleaux triangle, it appears that the above defining characteristics of a neighborhood color sequence suffice to characterize feasible neighborhood colorings. It remains to analyze 4- and 5-sided tiles.

      4. My program now gives 18 3-sided tiles, 46 4-sided tiles and 43 5-sided tiles. I am counting reflections as distinct. If I restrict to only 3 and 4 valencies I do get the right number of 5-sided tiles, but there is still room for error so don’t take these numbers as final.

        I will give a printout of the valencies and constraints and may try to render them

      5. Here is a link to the output from my program. The numbers not in brackets are the valencies of the vertices round the tile. The numbers in brackets tell you which vertex an edge between two vertices is constrained to. The number gives a relative position, so for example on a five sides tile (3) mean an edge has a constraint to be distance one from its opposite vertex’

        http://philgibbs.uk/out.txt

      6. Ah, I understand – that would give two edges of the other edges the same-colour neighbour.

      7. How about “6 (3) 6 (3) 6 (3) though? In general I’m not seeing why the following are not allowed:

        – more than one 6
        – a 6 and a 5
        – a total valency exceeding 20

      8. The tile “4 3 (2) 3” can be coloured but without using the constraint so we don’t count that. It will be assumed that all constraints are used when they are coloured. However, in a few cases a tile may be coloured in more than one distinct way that uses all the constraints. Those colour variations are not being counted as different tiles here.

      9. > The tile “4 3 (2) 3” can be coloured but without using the constraint so we don’t count that.

        I don’t think I understand. Surely the same would apply to 5 3 3, yet you do list 5 3 (2) 3.

        But conversely, my own guess at why you didn’t list 4 3 (2) 3 also applies to 5 3 (2) 3. If the central tile is coloured 1 and its edge-neighbours that share the 5-valent vertex are 2 and 3, and the other neighbours at the 5-valent vertex are 4 and 5, then the remaining edge-neighbour must be 6 – can’t be 4 or 5 because then one of the above edge-neighbours would have two edge-neighbours the same colour – so the edge between the two 3-valent vertices is not constrained. Hence you shouldn’t be listing 5 3 (2) 3. Right?

      10. Yes you are right 5 3 (2) 3 should not be listed. It probably requires running a mini SAT solver over each case to decide whether it can be coloured or not in a way that makes the constraints necessary

      11. Yeah, though a brute-force depth-first-search colouring should be quite fast enough for this purpose.

      12. > What are “all constraints”?

        The definition of a constraint I am using is that it is a relationship between an edge and a vertex of the same tile that requires the edge to be an arc of unit radius centred on the vertex. There can be at most one of these per edge but possibly more than one for one vertex. This is slightly different from your labelling notation which uses a relationship between an edge and another tile.

        I am claiming that there is no need to include a tile if it can only be coloured in such a way that some constraints are not needed to make the colouring valid as with 4 3 (2) 3

    1. Yes, you are right. That can be coloured in a way I had not accounted for. I will have to adjust to allow it.

      1. Yeah there may even be a need to adjust your representation. Cases like this (that can only be coloured by making two consecutive vertices of the central tile have neighbours the same colour) force the edge between those vertices to be of length 1, but do not say anything about fattening. I’m not sure how your representation can deal with that.

      2. Another constraint is that a 3-valent vertex cannot be flanked by edges both of which need to be of length 1, since then one or both of the edge-neighbour tiles would have diameter >1.

      3. I think cases where a diameter is length one on its own can be ignored provided we play safe on the colouring and allow two tiles to have the same colour if they both join a third tile at a vertices only. Any possible solution a search algorithm found would have to be further investigated by hand to make sure it is valid. If no solutions are found and we have played safe there is no problem. We would only have to try harder if there were lots of solutions that failed only for this reason when hand-checked.

        It is of course a good point and one we must remember to mention in any proof writeup.

  6. I’m wondering whether the following representation might cover all bases suitably economically/elegantly:

    – Represent an n-gon tile by a sequence of n numbers d_i chosen from {3,4,5,6} denoting the valencies.

    – Represent a constraint as a pair {v_i,v_j} or {v_i,e_j}. Geometrically, these are to be understood as (respectively) pairs of vertices or a vertex and a midpoint of an edge, that need to be 1 apart in the tiling. Call the set of constraints S.

    – We have the following constraints (so far). Assume indices are mod n.

    – – neither {v_i,e_i} nor {v_i+1,e_i} can be in S.
    – – if {v_i,e_j} is in S, {v_i,v_j} and {v_i,v_j+1} must also be.
    – – if d_i = 3, at most one of {v_i-1,v_i} and {v_i,v_i+1} can be in S.
    – – if d_i + d_i+1 >= 9, {v_i,v_i+1} must be in S.
    – – if d_i = 4 and d_i+1 = 3, {v_i,e_i+1} cannot be in S.
    – – if d_i = 4 and d_i-1 = 3, {v_i,e_i-2} cannot be in S.
    – – if d_i = 5 and d_i-1 and d_i+1 are both 3 and n=3, {v_i,e_i+1} cannot be in S.
    – – no 4-cycle of pairs of elements {v_i,v_j} can be in S.

    (Have I missed any?)

    I’m guessing that it should be fairly easy to enumerate the distinct (up to rotation) sequences d_i and the admissible associated S’s based on this representation. More importantly, I think it will leave less need to manually check cases than is the case with your current representation.

    What do you think?

    1. I may be misunderstanding your last condition but any two constrained diamaters {v_i, v_j} must intersect somewhere, possibly at a vertex

      1. {v_i,v_j} includes edges as well as diameters. This condition is a way of representing the problem you identified with Boris’s colouring of the 37-tile hexagon.

    2. I will try to correct my algorithm to use those conditions without the additional diameter constraints and then I will search to see which cases, if any, could have those constraints added in.

      1. Better (sorry about this!): no pair {v_i,v_i+1} and {v_j,v_k} can both be in S unless one or other of j,k = i or i+1.

      1. No – good one. That means we need to strengthen this rule:

        > if n=5 and d_i > 3 then d_i – 3 of {v_i,e_j} are in S, j in {i+1,i+2,i+3}.

        I think it is still optimal for n=5 but for n=3 or 4 it is more complicated.

  7. It’s becoming quite a lot of rules, and it would require checking each tile carefully to be sure we had not missed a rule. The alternative is to run a SAT solver on each tile with given constraints to see if it can be coloured.

    1. Maybe – though some of the rules arise from the need to keep the tile’s diameter down to 1. In fact I just realised that this:

      > no pair {v_i,v_i+1} and {v_j,v_k} can both be in S unless one or other of j,k = i or i+1.

      obviates this:

      > no 4-cycle of pairs of elements {v_i,v_j} can be in S.

      so that’s one fewer rule. Still working on strengthening the pigeonhole one.

    2. I think this is also a special case of the rule that any two constraint lines must intersect. If they don’t you get a diameter greater than one.

      1. It’s not a special case of that rule, it IS that rule 🙂 It doesn’t explicitly mention intersection of two diagonals within the interior of the tile, but it doesn’t need to, because with n at most 5 we can’t have a 4-cycle consisting entirely of diagonals – at least one of the four must be an edge of the tile. I think it’s just easier to encode it as I described than to talk about intersections.

    3. > The alternative is to run a SAT solver on each tile with given constraints to see if it can be coloured.

      It is not clear to me how to represent a tile with given constraints as an instance of SAT. Can you elaborate?

      EDIT: I just read the wiki. These rules seems rather SAT-friendly. Nice!

  8. Strengthening: replace “if d_i + d_i+1 >= 9, {v_i,v_i+1} must be in S” with “if d_i + d_j + min(|j-i|,n-|j-i|) >= 10, {v_i,v_i+1} must be in S”.

    1. Correction

      Strengthening: replace “if d_i + d_i+1 >= 9, {v_i,v_i+1} must be in S” with “if d_i + d_j + min(|j-i|,n-|j-i|) >= 10, {v_i,v_j} must be in S”.

  9. I think everything is now covered except the cases 4 4 4 and 4 4 3 3, which do not get any required constraints from the above rules but which by the pigeonhole principle need at least one {v_i,v_j} to be in S.

  10. Forgot to post this other strengthening: replace “if n=5 and d_i > 3 then d_i – 3 of {v_i,e_j} are in S, j in {i+1,i+2,i+3}” with “if d_i > 8-n then d_i + n-8 of {v_i,e_j} are in S”.

    1. I am getting a lot of tiles especially the four sided ones. I suppose one of these could be just what is needed to find a valid 6-colouring so it is worth persisting. I will need to do another iteration of the code to allow for the new types of constraint. Give me a few days.

      1. Can you include 1- and 2-sided tiles in your next iteration of the code? Presumably, these are straightforward, but if I’ve learned anything in the last couple of days, it’s that these constraints are surprisingly nontrivial.

      2. I just added a rule to accommodate what we know about the neighbourhood of 6-valent vertices: quads and pentagons can have at most one 6-valent vertex, because such vertices must have an angle of exactly 60 degrees.

      3. Where “angle” denotes the angle subtended by the neighbouring vertices, not the angle at which the tile edges emanate from the 6-valent vertex, of course.

      4. @Dustin: can you elaborate? What is a one-sided or two-sided tile? Are they (respectively) isolated points and paths of positive length but zero width? Why are they of interest?

      5. The edges don’t have to be straight so you can define tiles of one or two edges that don’t have zero area. It may be that once a full argument is presented these can be ruled out as unnecessary, but I don’t see any harm in including them in the list anyway.

      6. @Aubrey – Here’s an illustration of 1- and 2-sided tiles (in red):

        They are of interest because they will likely show up in an exhaustive search over plane graphs. I have no idea if there are any interesting constraints for these tiles, but I figured I’d point them out to the constraint experts in case something nontrivial pops out.

      7. In the case of the one sided tile shown would you not be able to colour it in green and so remove it? If this created a conflict with another green point somewhere then that point would already be in conflict with a point in the original green tile.

      8. Thanks both – yes, silly me. Philip typed the proof for the one-vertex case faster than I could 🙂 For two vertices I agree it is non-trivial. All I have so far is:

        – neither vertex can be of valency 6 (hexagon thing)
        – if both are 5, they must be 1 apart (pigeonhole)
        – if either is 3, they must be strictly less than 1 apart (diameter of edge-neighbours)

        This led me to another question though. Am I right in saying that all edge in any tiling can be harmlessly (i.e. without needing to change any tile’s colour to preserve the chromatic number) flowed into ones that are either straight or have constant radius of curvature 1 ? Can we devise a tiling (of any chromatic number) in which that is not so? (I ignore the one-vertex tile case.) I recall my error regarding one of my promising-looking tilings (see June 7th) – a radius of 2 could be used in places but it enlarged the exclusion set.

      9. I think another rule that needs to be added is that if you have an additional vertex-vertex constraint that is not associated with an edge-vertex constraint, then both vertices must have valency at least 4

      10. Thanks Philip. I’m not quite sure what you mean by “not associated with an edge-vertex constraint”. Do you mean, calling the vertex constraint {v_i,v_j}, that S does not include either a {v_i,e_k} or a {v_j,e_k} with respectively v_j or v_i (but not both) being a vertex of e_k ? If that’s what you mean then yes it’s certainly true, but I don’t see a case where we need it. Are you seeing cases that it excludes but the existing set of rules doesn’t, or conversely are you seeing rules that this rule obviates?

      11. I am thinking of a case like 3 3 3. There is no point adding a constraint between two of the vertices.

      12. When |j-i| = 1 we also don’t need an isolated {v_i,v_j} when d_i = d_j = 4, because if the vertex-neighbours at v_i and v_j are the same colour then the edge-neighbour has two edge-neighbours of that colour.

      13. Ah yes, good point – we should only list S’s for a given d when there is a colouring that relies upon all S’s constraints. I wonder if there are other such cases – I will think about that.

    1. Um – why does it need to be convex? I’m not succeeding in drawing a non-convex quadrilateral with two opposite edges of length 1 and the other edges and the diagonals no longer. (Unless the length-1 edges cross, but I’m excluding that case by making at least one of them be an edge of the tile.) What am I missing?

  11. Here is what I get if I use the rules in the Wiki, plus a rule to remove extra vertex-vertex constraints if one or both of the vertices has valency 3.

    Only extra vertex-vertex constraints that are not required by vertex-edge constraints are shown as pairs in curly brackets.

    Some more rules to remove unnecessary constraints are needed

    http://philgibbs.uk/out2.txt

    1. Yay! Let’s work through these.

      For n=2 we can lose 6 4 and 6 5 by the hexagon constraint. (Yeah, that’s not at the wiki, sorry! – I just added it.) Also we can have 5 4 without {0,1} – note I snuck an extra term into the “min” fuction in rule 7 this morning 🙂

      I see that the 4-4 rule I posted an hour ago can eliminate some cases. I also see some symmetry-duplicates – not sure whether you tried to remove those. Other than that I think it may be a SAT job to seek colourings of each case that use all the constraints.

      1. Hm, actually… I’m not sure it’s a good plan to remove cases where no colouring uses all the constraints. The issue is that we have some cases (such as n=2 and one of d_i = 3) where an inter-vertex distance is required to be strictly less than 1 (see rule 3, which I’ve just edited to handle the n=2 case). I think it might end up simplest to include both cases when the distance can be either less or equal.

      1. Thanks! What exactly is your latest rule to avoid unnecessary vertex-vertex constraints?

      2. I have required that the valency minus the number of edge constraints using the vertex must be greater than three, for both vertices. This might be too strong

      3. Hm, sounds ambitious – I’ll think about it.

        How many tiles do you get in total if you don’t impose any such constraint, only the ones at the wiki?

      4. I’m not understanding that. Sure it can be coloured – the central tile is 1, its edge-neighbours are 2,3 and4 , the vertex-neighbours of the length-1 edge are both 5 and the other vertex-neighbour is 6. Did you mean something else?

      5. If I don’t include these rules I get 325 quadrilaterals and 217 pentagons, so a lot more tiles

      6. Hm, only about twice as many – I was fearing worse.

        I think we need to change my rule 9 to “if d = {4,4,4} or {4,4,3,3} (or its rotations) then S must include a {v_i,e_j}”. Have you spotted any uncolourable cases that that would not exclude?

        > Must remove 5 4 {0,1} too

        Um – how is that not colourable?

        I guess now is the time to find a way to make a SAT problem out of the coverability of a so-far-unachieved area (say a disk of radius 3) with these tiles. Does anyone have any ideas for that?

      7. 5 4 {0,1} can be coloured but not in a way that needs the constraint

        5 5 4 {0,1} {0,2} {1,2} also need to be explicitly excluded

        I will see what difference your change to rule 9 makes.

      8. Wait – I now think rule 9 has to be the stronger “If d = {4,4,4} or d_i = d_i+1 = 4 then S must include a {v_i,e_j}” – i.e. it must also apply to 4 4 4 3 and 4 4 4 4. (The n=5 cases happen already via rule 8.)

  12. I think I have a way to SAT-encode the question of whether the plane can be covered using the tiles Philip has enumerated. It is a bit rough, but I think it’s ready for scrutiny by the SAT experts here.

    The first step is to decide on a finite region of the plane to examine. Recall that we’ve failed to 6-tile a disk larger than about 4.5 across. I think the easiest way to go is to give each tile a list of tile neighbours, where a neighbour can be 0 to indicate the “coastline” of an island that we want to tile, and then to encode the criterion that there must be a tile that is k steps away from the coastline. (I’m going to call such a tile “k-Uzbek” in honour of the fact that Uzbekistan is the only country in the world – well, actually there is also Liechtenstein, but “Liechtensteiner” is a lot longer than “Uzbek” – that possesses neither a coastline nor a border with a country that has a coastline.) We can ordain that the exterior of the island is 0-Uzbek and a tile with k-Uzbek neighbours but no x-Uzbek ones for x<k is (k+1)-Uzbek; that seems SAT-encodable.

    Then we encode Philip's list so that each item consists of:
    – a set denoting which of its neighbours are edge-neighbours (this always includes neighbour 1; neighbours are indexed in clockwise order)
    – a set S of pairs of neighbours that are allowed to be the same colour

    Next we say that there are n tiles, indexed 1..n, where each tile has:
    – an index from Philip's list
    – a list of 3..12 neighbour indices (the number being dictated by the Philip index)
    – a colour 1..6

    The conditions for the SAT problem, other than the existence of a k-Uzbek tile, are then:

    – no tile has any neighbour other than 0 more than once, except that the subsequence {x,y,x} is allowed when tile y has only two vertices

    – neighbourness commutes, without convexity conflicts. That is: if the x-th neighbour of a is b, and x is an edge, then there must be a y for which the y-th neighbour of b is also an edge and is a, such that either x does not appears in any member of a's S or y does not appear in any member of b's S.

    – vertices of the tiling are well-behaved in terms of the subsequence of each tile's neighbour indices between each consecutive pair of its edge-neighbours. Basically, this means that if the sequence betweeen a consecutive pair of edge-neighbours of tile x is {n_1..n_y} (with n_1 and n_y being edge-neighbours of x), then that between some consecutive pair of edge-neighbours of tile n_1 must be {n_2..n_y,x}, and that between some consecutive pair of edge-neighbours of tile n_2 must be {n_3..n_y,x,n_1}, etc, with wraparound occurring after exactly y steps.

    – all same-coloured pairs neighbours of a tile are among the pairs listed as allowed to be same-coloured

    I think a way to start would be with k=3 and n=26, which would be satisfied by Philip's pentagonal construction, and then to increment n. I don't think that construction can be extended arbitrarily far even in one dimension, and the best constructions that can be thus extended have no 3-Uzbek tiles, so there may be a maximum n for which k=3 can be solved, which would be a quick route to an answer. If in fact we find otherwise, we go to k=4, but with the confidence derived from seeing that the program works 🙂

    Thoughts? Is there anything hard to SAT-encode in the above? Feel free to say that the above is thoroughly unintelligible – it's late…

    1. > I don’t think that construction can be extended arbitrarily far even in one dimension

      Ah, of course it can perfectly well be extended arbitrarily just by a chain of 0-Uzbek tiles. Perhaps we can get what I was intending by increasing the required number of 3-Uzbek tiles in synchrony with increasing n.

    2. When you talk of neighbours do you mean just the neighbours that are joined at an edge or also neighbours that are joined at a vertex only? I will assume the former unless you correct me.

      Rather than jumping straight to k=3 I would suggest first exploring k=1. If a tile cannot be 1-Uzbek then it cannot be in any complete solution. I’d like to know how many (if any) can be eliminated by this logic.

      It may then be worth looking at k=1.5 allowing edge and vertex neighbours but not the full set of k=2 neighbours.

      It may also be worth exploring vertex centred and edge centred islands.

      1. No I meant both edge-neighbours and vertex-neighbours – that’s why there are up to 12 of them. Regarding smaller k, well, with SAT we are trying to attack the whole problem at once rather than testing each tile sequentially, but yes, if we can eliminate a lot of tiles at the k=1 stage then that would make for a smaller SAT problem at k=3 so I agree.

      2. I see I got my Uzbek numbers confused and thence confused yours; for avoidance of doubt let me correct things. Let a tile be k-Uzbek if it is k steps from the ocean in a particular tiling of an island; let it be k-Uzbekable if there exists any tiling of an island in which it is k-Uzbek. If the ocean is 0-Uzbek, then all tiles of any description are 1-Uzbekable. The search you are currently doing is to identify tiles that can be completely surrounded (here I include the vertex-neighbours as well as the edge-neighbours) by other tiles, which is the definition of 2-Uzbekable tiles. The next step will be to eliminate (iteratively) any 2-Uzbekable tiles that cannot be surrounded by other 2-Uzbekable tiles; since such tiles cannot be 3-Uzbekable. And so on.

    1. Thanks! Just under 500 total. Looks like my new rule has all but prevented pentagons from having any 6-valent vertices: that could be useful down the road.

    2. Ah, I just noticed that “5 4 {0,1}” is not present in your latest list. Are you sure you removed all conditions that say constraints have to be used?

      I also just realised that my rule 5 should be removed entirely, because it is only needed under the assumption that {v,e} constraints are always used. Can you rerun without it?

      1. It still needs some fixing up.

        What I have done now is I have implemented a simple algorithm that looks for colourings of a single tile. This has removed some tiles that we had not noticed could nlt be coloured. It also means that I can remove most of the rules whose purpose is only to check colourings. This will simplify the algorithm and reduce scope for errors.

        I will give another update soon so you can see what has changed.

      2. Great. Yeah, the rules are just a means to an end really. I wil certainly be interested to see which tiles we had not noticed could not be coloured (and to understand why they can’t).

      3. Thanks. Ah, I see from these (and should have noticed earlier) that you’re listing both clockwise and anticlockwise versions of tiles that have a chirality. It’s probably worthwhile to eliminate those duplicates.

      4. I had not updated your rule 7, now that I have the only uncolourables you miss are “5 5 4” and “4 5 4 (3) 3 {0,1} {0,2}”

  13. Here is a new list. I have allowed some tiles with edge-vertex constraints that are not used. I am not sure if that are any use but for consistency with other constraints they are there.

    http://philgibbs.uk/out6.txt

    I am not a SAT solver expert but I can program colour searches in Java. it might be less efficient but we will see if that matters

    1. I am going to do a spreadsheet of all tiles including many that fail, using just the main rules to eliminate from the list. It will show numerical and logical characterises and any rules they fail on. This will allow us to select tiles for specific algorithms without having to run black box code and will make it easier to track the logic if and when we come to write up a proof.

  14. @Boris (and all others SAT-savvy here, but mainly Boris!): I think I may have a neat new way to find good tilings with your pixel-based approach.

    We are for practical purposes working with map-based colourings, and indeed with ones that do not have Siamese tiles. In this circumstance, we can describe an “epsilon-proper” colouring of a tiling as the property that for some small positive number e, a pair of pixels can be the same colour only if:

    a) their centres are less than (say) 0.6 apart
    OR
    b) their centres are less than 1 apart and there is another “bridging pixel” of that same colour whose centre is less than (say) 0.7 away from both of them
    OR
    c) they are more than than 1-e apart and there is no such “bridging pixel”

    When e=0, this reduces to the usual criterion. But when e is positive, tilings are easier; for example, since the standard hexagonal tiling can be 4-coloured with same-coloured tiles being sqrt(3)/2 of their diameter apart, we should be able to SAT-solve the above with arbitrarily large areas and only four colours when e = 0.2 (so long as the pixels are fairly small).

    The strategy I’m thinking of, therefore, is to use a nice large area, like 6×6 (and pixels as small as you can computationally manage) and see what happens as you reduce e (while allowing six colours, of course).

    Does this sound promising?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s