Polymath16, eleventh thread: Chromatic numbers of planar sets

Posted on by Dustin G. Mixon

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

– Let w(k) denote the supremum of w such that [0,w]\times\mathbb{R} is k-colorable. Then of course w(1)=-\infty and w(k)=\infty for every k\geq 7. Furthermore,

\displaystyle{w(2)=0, \quad w(3)=\frac{\sqrt{3}}{2}, \quad w(4)\geq\sqrt{\frac{32}{35}}, \quad w(5)\geq\frac{13}{8}, \quad w(6)\geq \sqrt{3}+\frac{\sqrt{15}}{2}.}

Colorings that produce these lower bounds are depicted here. The upper bound for k=3 is given here.

– The largest known k-colorable disks for k=2,3,4,5 are depicted here.

Presumably, we can obtain descent upper bounds on w(4) by restricting (a finite subset of) the ring \mathbb{Z}[\omega_1,\omega_3,\omega_4] to an infinite strip.

120 thoughts on “Polymath16, eleventh thread: Chromatic numbers of planar sets”

  1. For completeness, let me just re-record here that Philip’s disk for k=6 is shown here:

    https://dustingmixon.wordpress.com/2018/06/16/polymath16-seventh-thread-upper-bounds/#comment-4851

    I’ve been trying to deform it in such a way as to cover a sphere with two copies of it, suitably juxtaposed, but I haven’t succeeded yet. If this were possible it would be of interest, because as of now the best tilings of surfaces of spheres are extremely boring (tetrahedron, square pyramid, dodecahedron) with the sole exception that a sphere of circumference exactly 4 can be 4-tiled as an octahedron.

    Another line of enquiry that might be interesting is to identify tight bounds on k-colorable regions other than infinite strips. For example, we currently have that a rectangle exceeding 1 x \sqrt 3 cannot be 3-tiled (because a 4-chromatic UD graph can be drawn inside it); do we have a way to 3-tile a rectangle of exactly that shape? What about other shapes?

    Reply

      1. I don’t have a picture of it, but it is derived from the tesselation of the plane with two distinct tile shapes (the one that Tom showed was not quite 7-tileable): centre a pair of curved triangles at each vertex of an octahedron, then three of the other shape (as opposed to four for the plane) can meet at the centre of each face of the octahedron.

      2. Hm, which Tom’s tessellation or tile shapes did you mean? I don’t understand, sorry. Did you replace every face of octahedron by 4 tiles?

      3. Oh, yes, every vertex gives 2 tiles and every face 3 additional tiles, 12+24 tiles in total.

      4. Sorry. I meant the tessellation in:

        https://dustingmixon.wordpress.com/2018/08/28/polymath16-tenth-thread-open-sat-instances/#comment-5778

        Let the tile coloured black in the left-hand panel be A and the one coloured black in the right-hand panel be B. Then place two A’s symmetrically at the North pole of the sphere, so that the pole sits at the centre of their shared edge. Do the same at the South pole and at four points on the equator, and orient them perpendicular to each other in the same way as for the plane. Then each face of the octahedron has three of tile B meeting in its centre and three halves of tile A at its corners.

      5. I was for a second earlier;) Yes, I got it. Here is a Picasso projection of what you mean. Apologies for handmade picture. Two upper and two lower tiles are the same ones.

  2. Since previous thread is not active already, I will repost here my question.

    Consider any periodical tile based tessellation. For such tessellation there exists some colored pattern by witch one can cover the plane back to back using translations only.
    Is it true, that for any periodical tessellation one can find “one-dimensional” pattern?

    Other words, one can convert any initial pattern to almost straight connected string with the same set of colored tiles. Single vertex connections are allowed.
    Some special cases, which cannot lead to reducing of colors number, such as surrounding of some tile by other tile, are out of the question. (One can include them with some reservations.)

    Reply

  4. There is another tessellation with rational coloring number k_r=6\frac67, based on Pritikin’s design with diamonds decimation sequence (1100110). Four other examples are listed here: https://dustingmixon.wordpress.com/2018/08/28/polymath16-tenth-thread-open-sat-instances/#comment-5685 and here https://dustingmixon.wordpress.com/2018/08/28/polymath16-tenth-thread-open-sat-instances/#comment-5702.
    For all of them there exist one-dimensional colored pattern with 7th color period equal to 8. It may be noted also, that momentary period could be exactly 8 for all tessellations, except for Pritikin’s, where it takes two values: 3 and 13 (or some other odd values, depending on the pattern direction).

    I have found also tessellations with other values of RCN, namely k_r=6\frac{9}{11}, 6\frac45 and 6\frac34. Corresponding decimation sequencies are (11001100110), (110011001100110) and (1100). Color ratios are 11^6:9, 5^6:4, 4^6:3. It seems all of these tessellations are valid. One need to check them.

    Reply

    1. One can exchange blue and cyan tiles in one of the 4-tiles row (4th and last) of Tom’s pentagonal 7^6:6-coloring. This will give regular blue coloring (it is a special color).

      Reply

      2. That’s great! It is interesting also to get solutions for opposite task: finding a coloring with the largest most-used-color-ratio. The conjecture is that it cannot be more than 1/6. Or will such question give the same set of color ratios, you have found already?

      3. I added results for the maximum density for 1 color (leaving all other tiles uncolored). It seems that .15 is the maximum density for the pentagonal tiling.

      1. Thanks! – um but are you sure it works? Look at the tile coloured 3 whose botom-left corner is at the origin is closer and the tile coloured 3 that is at “one-o’clock” from it. They seem to be inescapeably closer together than the diameter of the tile coloured 4 that sits between them.

      1. Sorry for being too fast for you 🙂 A good thing is that even though no one except Dustin can edit their own posts, we CAN overwrite files in the dropbox, and the new version does indeed replace the old one in pre-existing posts linking to it. (I have silently corrected my own mistakes several times by this means!)

      2. Thank you, Aubrey. You are extremely fast;) Why bugs are obvious olny after posing?
        It seems, it cannot be corrected. One need to think and try 11^6:9-coloring first.

      4. I’ll do it a bit later. Better I’ll start with simple case.
        Here is a tessellation with 7^6:6-coloring and k_r=6\frac67. (I’m not sure already;)

      7. Other announced tessellations have internal conflicts and require more attention to overcome them (if it is possible at all).

    4. I suggest following notation for 2-colored (or bichromatic) tile chains: v – vertex, e – edge, […] – finite chain, (…) – infinite periodic chain. Examples: [eve] – finite 1e2v1e2-chain, [evvve] – finite 1e2v1v2v1e2-chain, (v) – infinite 1v2v1v2v…-chain, (ev) – infinite 1e2v1e2v…-chain, where 1 and 2 are tile colors. Examples of allowable chains: [eve], [evvve], (v). Examples of invalid chains: [ee], [vev], (ev).

      Reply

    5. Some explanations and illustrations for “dash-dot” approach.
      One can take 7-colorable Pritikin’s tessellation, then remove and/or combine some diamonds to get required property, for example, to minimize (or maximize) 7th color density. One can do it in two steps.
      At the first step, one get sketchy Pritisin’s style construction, which shows initial tiles placement. First thing one should do here is to minimize number of conflicts (invalid chains).
      Example of such construction with no conflicts for 7^6:6-coloring is shown below. One can see here allowable [eve]-chains (some of them shown by dotted lines).
      At the second step, one convert this construction to valid tessellation by means of tiles boundaries correction. Such operation is not always possible due to second order conflicts.

      The next example is a sketch for 11^6:9-coloring. There appear invalid [eveve]-chains here (dashed lines). At the first sight it is easy to overcome them via changing middle edge to vertex (marked by small circle). But this operation affects many neighbor tiles. Consider a set of tiles, marked by dotted circle. It seems, the only way to start is to place all 6 tiles into circle with unit radius. This, in turn, requires further transformations of surrounding tiles and might lead to the failure of entire operation.

      Best sketch for 4^6:3-coloring, I’ve found, contains about 3 times more [eveve]-chains:

      Reply

  6. There is a simple claim, that might be useful:
    If some vertex connects tiles with c different colors and only k colors are used in tessellation, then unit circle with the centre at this vertex can be crossed only by at most k-c remaining colors.
    (This is due to the fact, that such unit circle is contained in exclusion zones of all c colors.)

    For example, it is easy to show, that all three Aubrey’s tessellations should have at least 7 colors. For first tessellation one of the 4-valent vertices corresponds to unit circle, crossed by 3 tiles, every two of which cannot have the same color, hence k\ge7. Second tessellation has 5-valent vertex, and corresponding unit circle is crossed by 3 tiles, which cannot have the same color simultaneously, hence k\ge7.
    For pentagonal tessellation c=4 (tiles 1…4 on picture below), hence for k=6 four nearest tiles should be colored by 2 remaining colors (5 and 6). Similarly, tiles A and B should have color 1, therefore tile C cannot have color 1…6 and tessellation requires at least k=7 colors.

    Reply

    1. Yeah – this looks like a simple observation but it may be quite powerful – it may give rise to a way to streamline the search that Philip has been working on for ways to juxtapose tiles. Philip, are you out there? How is that work going?

      Reply

      1. Hi I am still out here but have been distracted by so many other things. Still hoping to get back to this though.

  7. A little bit cleaner picture of 6-flower (Philip’s disk) is shown below. One can see here a skeleton from five connected regular pentagons with unit edges (dotted lines). Minimum radius of 6-flower is r=\frac{1+\sqrt5}{2} \sqrt{\frac{15+\sqrt5}{10}} \approx 2.12426.

    Reply

      1. I looked at that some time ago but I couldn’t find a useful way forward – but I agree that it deserves more exploration. Since spindling at distance phi equates to a rotation of pi/5, i.e. a rational proportion of a circle, we can quite easily get graphs that have a lot of “unplanned edges”. But I didn’t succeed in finding graphs that have an edge density exceeding the graphs we’ve been mainly focusing on (i.e. ones with a high density of Moser spindles).

  8. Hey everyone,

    Things have gone a bit quiet here, so I wonder if it might be useful if everyone could post a little update on the status of their work. I’m hoping that quite a few of you are quietly beavering way on one or another aspect of the approaches we’ve been exploring. Don’t be shy!

    Reply

    1. Yeah, that’s definitely the case for me. Though I’ve been following this thread, there’s just not much I can add here or post myself currently.
      I’m still working on my plan to make some actual plots of how certain variables affect chromatic number, based on the really helpful posts from Jaan and Tom in the previous thread. I feel though that this still might take the one or the other month to really bear any demonstrable fruits.

      Aside from that, now that the n-ball graph approach to explaining why tile-based colorings are necessary feels rather complete, I’ve returned to tackling the topological approach to the same issue, using punctured neighborhoods again.
      It has felt too deceptively simple the last time I seriously worked on it (at the start of this year), but putting the n-ball approach together has given me new certainty that there’s mileage to that approach too.

      Reply

    2. Not much news around here either, I guess otherwise people would post. One little good to know fact that was pointed out to me by Laczkovich today is that the https://en.wikipedia.org/wiki/Tarski%E2%80%93Seidenberg_theorem can be used when we consider (1,d)-distance graphs. A consequence of the theorem is that in case of a system of polynomial equations in (x1,..,xn,y1,..,yn,d), the values of d for which there is a solution forms a union of intervals such that both endpoints of each interval is an algebraic number. This implies that for every transcendental d and finite graph G there is an \varepsilon such that if G is a (1,d)-distance graph, then it is also a (1,d’ )-distance graph for every d-\varepsilon<d'<d+\varepsilon. This was conjectured by Tamas Hubai about a year ago. (In fact, he also conjectured the stronger statement that instead of transcendental numbers, this also holds for non-constructible numbers – I don't know whether this also follows from algebraic geometry.)

      Reply

    3. I have to many questions to afford to be not shy.
      Maybe you know about new fractional CN record, 3.8992: https://arxiv.org/abs/1810.00960.
      Thanks to Aubrey and D.E. Knuth I finally understand how to calculate CN for large graphs using SAT, but I still don’t know how to get fractional CN. Probably it will be interesting to calculate it for known 5- or almost-5-chromatic graphs.
      I reread first threads trying to find the answer, what does it take to be 5-chromatic? There is a lot of thoughts here, which I cannot understand before, but I still haven’t a clear picture. What is essential here? Spindles density, edges density, vertices number, rotations set, something else?
      I plan to define spindles density for known graphs. Is there some theoretic bound for spindles density s/v? How does it relate to edges density e/v? Here s, e, v are the numbers of Moser’s spindles, edges and vertices. The best known bound for edges is e \le v^{4/3}, see interesting pictures here:
      https://math.stackexchange.com/questions/1986369/erdos-unit-distance-problem-maximal-graphs?rq=1

      Reply
  9. Pingback: 6-colourings of subsets of the plane | Complex Projective 4-Space
  10. Pingback: Updates and Pictures | The polymath blog

  11. Thanks Jaan! I, for one, had not heard about the new FCNP record. It’s nice to see that the same kind of thinking that led me to the original 5-chromatic graph has related uses. The authors don’t seem to say that theirapproach has reached diminishing returns, so I infer that the key milestone of a FCN exceeding 4 may be within reach!

    We have not worked much on spindle density, but one interesting feature is that the spindle density I was able to achieve is actually a bit lower for the 5-chromatic graphs arising from the 30 unit vectors in my graph V than for the graphs arising from the original 18 unit vectors (those in the graph U). I’m unaware of any attempt to identify a theoretical upper bound.

    Also, note that the upper bound on e is actually o(1) more than the 4/3 power of v. I believe that only one graph has ever been discovered that exceeds 4/3, though – it has 16 vertices and 41 edges and is due to Ed Pegg:

    https://math.stackexchange.com/questions/2575268/maximally-dense-unit-distance-graphs

    Reply

  12. Hi everyone,

    I’ve been reading the paper that Jaan pointed us to with the new record for the fractional CN of a unit-distance graph in the plane. A notable lemma in the paper is that this FCN translates into an upper bound for the density of a set in the plane that avoids distance 1. It occurs to me that there might be something to extract from the reciprocal (no pun intended!) statement, i.e. that the Croft construction (density 0.2293) imposes an upper bound of about 4.36 on the FCN of any UD graph. Can that be translated into an upper bound on the standard CN? I don’t know nearly enough about what is known about fractional CNs, but I’m wondering whether there is anything that can be said about (for example) graphs whose CN exceeds their FCN by more than 1 (starting with any example of one, which I have so far failed to discover). Might this be a way to narrow the search for a 6-chromatic UD graph?

    Reply

    1. Landon Rabern just pointed me to the Kneser graphs K(n,k):

      http://mathworld.wolfram.com/KneserGraph.html

      which have a CN of n-2k+2 and a FCN of n/k. So for example K(12,4) has CN=6 and FCN=3.

      Nonetheless, seems like there are not very many (classes of) such graphs. Maybe this can be used as a way to narrow the 6-chromatic search space.

      Reply

      1. Ah, but these graphs are not UD! – thanks to Landon for noticing his own oversight in my question to him, which I then proceeded to overlook myself.

        Hm, OK, so this seems like a nice challenge: what is the largest value we can obtain for CN-FCN of a UD graph in the plane? As a start, can we find a 4-chromatic UD graph that has FCN less than 3? The Moser spindle has 7/2, the Golomb graph has 10/3, but all work that I’m aware of has been focused on maximising rather than minimising the FCN. Maybe graphs with large girth are promising, since odd cycles have CN=3 and their FCN converges to 2 as the order rises – but that doesn’t get CN-FCN above 1.

      2. I think all 5-chromatic graphs that we know have FCN less than 4. And here is the answer to your question.

  13. No, I think, Bellitto, Pecher and Sedillot and others checked these graphs first (at least Heule’s graphs, which have the same order as their 607-vertices 4-chromatic graph with \chi_f \approx 3.8992). And you are right, one can check some of 4-girth graphs. They are small enough (the record is 17 vertices only, as I know) to try to color them by hands.
    But I have another question (which shows, that I don’t understand fractional coloring well). Suppose we have two or more identical graphs G_1 with some FCN \chi_f(G_1). Then we build combined graph G_2 by some connection of graphs G_1. Is it true, that \chi_f(G_2) \ge \chi_f(G_1) for any graphs G_1 and G_2?

    Reply

    1. I tried it by hand, but without success. Because Exoo-Ismailescu’s 17-vertex graph has actually \chi_f =3 (I wrote a simple program to calculate it, I hope without bugs). But Hochberg-O’Donnell’s 23-vertex fish graph has \chi_f =2\frac78 and \chi = 4.

      Reply

    2. Hochberg-O’Donnell’s 40- and 45-vertex graphs (see Soifer’s Coloring Book, chapter 15) have \chi_f =2\frac34 (and use 35 and 45 colors), 56-vertex graph kills my computer.

      Reply

  14. I have some questions about SAT possibilities in application to graph coloring problem. The main question is how large could be the graph to be processed successfully (in the task of 6-chromatic graph seeking)?
    I tested almost all known 5-chromatic graphs. Processing time of relatively small graphs (up to 3000 vertices) varies from few seconds to few minutes for 4-coloring test and is less significantly for 5-coloring. The interesting exception is 1585-vertices graph, which stayed unchecked by Mathematica 10 (I aborted processing after 8 hours). Thanks to Tom I can try Glucose too, it finished successfully in about 7 minutes. Large graphs (more than 3k vertices) act differently: 6937- and 20425-vertices graphs finish successfully in few minutes with 4-coloring test, but they fail to finish with 5-coloring test (terminated after 10 hours). What does it mean? Should we use some other SAT-solvers? Or more powerful computers (I have i7-2670QM CPU, 2.2GHz, 6Gb RAM)? Or tune accurately some options of SAT-solver (more than 40 for Glucose)? Or perform some graph preprocessing (in addition to vertices ordering and symmetry breaking)?

    Reply

    1. Marijn Heule wrote (in Proceedings of SAT Competition 2018) that 5-coloring of graph S_{199} \oplus \theta_4(S_{199}) is hard. Should we interpret it so that maximum order of graphs we could analyze is about 10^5?

      Reply

      1. SAT is definitely easier than UNSAT for graph coloring. In my experience with UD graphs, it is the edge density that determines the performance of complete tools: the higher the edge density the easier the (UN)SAT problem. If the edge density is low and also when the graph is large, it is much better to use incomplete tools that can quickly find colorings — although they cannot proof UNSAT. One of the most effective incomplete tools for UD graphs is yalsat, available at http://fmv.jku.at/yalsat/

      2. Thank you, Marijn.
        How fast did you process S_{199} \oplus \theta_4(S_{199})? What hardware/software did you use? (Could you publish vertex coordinates of S_{199}?)
        What was the largest and/or hardest graph you have tested successfully? (I need it to have some fulcrum.)

      3. I added the vertex coordinates and the edges of S_199 to https://github.com/marijnheule/CNP-SAT . For testing whether a graph is k-colorable I simply use my laptop with yalsat for the SAT instances and glucose for the UNSAT instances. The solving time is rarely the bottleneck. Computing the edges using mathematica typically takes much more time. I am able to deal with graphs up to say 30,000 vertices. If there is a way to compute the edges efficiently, then I would be able to handle larger graphs.

      4. Really? I thought you used mega-clusters of computers. Maybe because Tamas wrote about 7-fold Minkowski sums (https://dustingmixon.wordpress.com/2018/04/22/polymath16-second-thread-what-does-it-take-to-be-5-chromatic/#comment-3996) and I thought they should give very large graphs.
        Yes, Yalsat works well, but I’m afraid it is because we are still far from 5-coloring UNSAT. Thank you for links and interesting information.
        Edge density is important, but probably not most significant. I checked with Glucose some medium 5-chromatic graphs with number of vertices/edges {6901/50238, 6937/44439, 7075/41163, 10585/67161, 20425/151311}. The averaged processing time for UNSAT-issue (4-coloring) was {8, 250, 18, 16, 16} seconds respectively. Here the edge to vertex ratio is {7.28, 6.41, 5.82, 6.34, 7.41}, ratio of their logarithms {1.225, 1.210, 1.199, 1.199, 1.202}, so correlation is not so obvious. SAT-issue (5-coloring) was successful only for 7075-vertex graph in Glucose (44 seconds).

      5. I use the cluster to compute small UD graphs with chromatic number 5. Minimizing a graph while preserving its chromatic number is much harder compared to determining the chromatic number.

        I was referring to the runtimes on SAT instances. I encountered several small graphs (a few hundred vertices) with a low edge density for which glucose had severe difficult finding a 4-coloring (say runtime of an hour). This was before I started to use yalsat for SAT instances. The runtime on UNSAT instances is much more stable and depends for a large part on the quality of the symmetry breaking.

      6. I tried various symmetry breaking colorings and vertices enumeration schemes. It seems the best choice is to paint the triangle with vertex (0,0) (rather than triangle with maximum sum of vertex degrees for example). I tried also BreakID for static symmetry breaking, the timing results were not always better.
        For verification: graph S_{199} \oplus \theta_4(S_{199}) has 39601 vertices and 391857 edges. Processing time in Glucose (4-colors test) was 428 s, in Yalsat (5-colors test) – 334 s. After preprocessing by BreakID – 456 s and 273 s respectively.

  15. I have a new quest for the masters of unit-distance graph creators. Is there a 5-chromatic graph on a unit radius sphere? So I would like all vertex coordinates to satisfy x^2+y^2+z^2=1 and the squared distance between two vertices is just (x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2. Note that this would give a 7-chromatic graph in \mathbb R^3 with a bichromatic origin. I wonder if the spherical equivalent of some Minkowski-sum type constructions can work.

    Reply

    1. I’m not at all sure about this, but I think I have an idea how you could prove that the chromatic number of the unit sphere is 4.
      First, note that the unit sphere can obviously be 4-colored so that no two antipodal points receive the same color: Simply color one open hemisphere with color 1 and the complimentary open hemisphere with color 2. Then color one half-open half-circle of the remaining unit circle with color 3 and again the complimentary one with color 4. Lets call this coloring c.
      Let S^2 denote the unit sphere. Now there are covering maps f : S^2 \longrightarrow S^2 that wrap the unit sphere around itself any given number of times, so we can choose one that wraps around six times, and I believe it ought to be possible to choose one that is an isometry. Consequently, the image under f of the two endpoints of a sixth of a great circle — i. e., two points a unit distance apart — are two antipodal points. Now simply give every point p the color that f(p) receives under c.

      Reply

      2. On second thought, this probably can’t work, since, if I am not mistaken, it is possible to 3-color the sphere so that no two antipodal points receive the same color, so if the argument above worked, it would imply that the chromatic number of the unit sphere is 3, which is impossible by the icosahedron example below. Sorry.

      3. The unit-edge length icosahedron doesn’t embed to the unit radius sphere, so some coloring might work. But I’m not sure I understood your construction. Specifically, it ought to work for any radius, and that is suspicious.

      4. Sorry for the long delay in posting this answer. The idea behind the construction was the following: Suppose I know that the unit circle has a 2-coloring c so that no two antipodal points receive the same color under c, and I want to prove that it can also be 2-colored so that no two points at unit distance receive the same color. Then one can do this as follows:
        1. Take the function f defined by f(e^{\pi i x}) = e^{\pi i 3x} (for real x).
        2. Color p with the color that f(p) receives under c.
        This works, since f maps points at unit distance to antipodal points (by wrapping the circle around itself three times). The idea was to do something similar for the two-dimensional unit sphere. Regarding your comment that this is suspicious because it ought to work for every radius, I don’t think this is true: It only works when the radius is such that the angle between points on the sphere that are at unit distance from each other divides \pi, since they will only then be mapped to antipodal points by a covering function. I was also suspicious of the construction, because, as noted above, I thought for a moment that the unit sphere can be 3-colored so that no two antipodal points receive the same color, which would mean that one could apply a similar construction to prove that the unit sphere could be 3-colored so that no two orthogonal vectors receive the same color, which is known to be false. Can the sphere in fact be 3-colored such that no two antipodal points receive the same color? I don’t know, and I guess my construction stands or falls by this question.

      5. I just realized that the sphere can obviously be 2-colored so that no two antipodal points receive the same color, which means that everything I wrote was nonsense. Sorry.

  16. Hm… that seems unlikely to be any easier than finding a 5-chromatic UD graph in the plane. Do you see any reason why it might be easier?

    Reply

      1. Well, actually I think it is quite likely to be harder, because we don’t have triangular grids any more. My construction relied critically on the fact that a unit-edge hexagon can only be 4-coloured in a few ways, and (somewhat to my disappointment) we haven’t yet found anything 5-chromatic that starts from a radically different basis (such as regular pentagons).

      2. I’m not so sure. Now we know constructions that use only the Minkowski sum of some carefully chosen unit vectors (like V\oplus V\oplus V), these don’t rely on initial observations about the hexagon and the triangular grid, but only on the fact that there are many unit-edges that appear in them. (Although implicitly properties of the triangular grid are certainly used.) Something like this should also give many unit-edges if the radius of the sphere is properly chosen. So maybe first the problem should be solved with any radius instead of 1.

      3. That would certainly be a lot easier. A vertex plus its neighbours of an icosahedron is already 4-chromatic, and I bet it can be spindled in productive ways. Butit wouldn’t lead to any useful biochromatic-vertex results, right?

  18. Actually I’m beginning to wonder whether there might be promise in Domotor’s suggestion to look at the unit-radius sphere. The vertices of a unit-edge cuboctahedron lie on it, and include four hexagons; the only one way to colour it with three colours assigns each colour to four vertices that lie on a square whose diagonals pass through the centre of the sphere, so a simple spindling of two copies that have two opposite “poles” identified gives something 4-chromatic with 22 vertices. It’s easy to see that adding other hexagons can give a pretty edge-dense structure; I haven’t got to 5-chromatic yet but I’m starting to think it should be doable, maybe even with fewer than 100 vertices (though I’m not expecting it to reach the 57 that would be needed to beat my 59-vertex 6-chromatic construction). I wouldn’t even want to bet against a bona fide 6-chromatic graph based on this sort of thing.

    Thoughts?

    Reply

    1. I think this is very exciting, with Tamas we’ve only noted sadly that the radii of the circumspheres of the platonic solids is not 1. He’ll try to check if taking sum rotations of the cuboctahedron can give a 5-chromatic graph.

      Reply

      1. Excellent. I’ve been travelling and unable to make time to look at this other than in my head, but there does seem to be quite a lot to try. One useful fact is that in a 4-colouring of the cuboctahedron no hexagon can be coloured with just two colours (“2tri” as we were calling it months ago) because that would force the two triangles to use three other colours. I’ve been trying to get stronger results, like eliminating 1tri by combining multiple cuboctahedra, but without success so far.

      2. PS: an efficient way to add vertices in quite edge-dense configurations seems to be to reflect the entire structure in a hexagon. This introduces new hexagons and can thus be iterated. I’m somewhat optimistic that this might lead to structures whose 4-colourings all have a property that invites spindling.

      3. Also, there may be scope for building something out of multiple unit-radius spheres with centres 1 apart. I’m keeping in mind the potential to use my 20-vertex clamps to enforce 6-chromaticity of subgraphs, though as yet I am not seeing a good way to use them (since they only enforce that either one of the clamps or the clamped thing must use six colours).

  19. Ah, sorry – check back for my description of a 59-vertex 6-chromatic graph in R^3. Basically I take two copies of Nechushtan’s (2000) “basic construction” and spindle them so that the two copies of his flap (the thing that he rotates to get his torus) can have their tips merged and still be mobile relative to the main structure. That 20-vertex thing, which I call a clamp, then has two vertices whose separation can vary between about 1 and 2.5 and that must be different colours in any 5-colouring. Thus, any graph with six vertices all pairs of which are between about 1 and 2.5 apart can be “clamped” – each pair not exactly 1 apart being identified with those two vertices of a clamp – and the result is a graph in which either the six-vertex “scaffold” uses six colours or else one of the clamps does (because its clamping vertex pair are the same colour). The obvious scaffold is of course the unit-edge octahedron, which requires just three clamps, giving a total of 60 vertices. (Then rotation can lose one of them, but that’s a boring detail.)

    Reply

  20. If we anyhow assume that the bichromatic origin conjecture is true, then we might as well assume that it’s also true on the sphere. Hopefully this would significantly reduce the size of a 5-chromatic graph, just like in the planar case. So the new task would be: Is there a unit-distance graph on the surface of the unit sphere such that we cannot 4-color it if the origin (a given special vertex) needs to be given two colors?

    Reply

    1. Yep. (Let’s call the special vertex the south pole, though, not the origin, so that people don’t jump to the conclusion that it is the centre of the sphere.) We got down to 26 vertices for this without the half-plane restriction, right? And hang on, I thought you had a proof for the panar version? – what am I forgetting?

      Reply

      1. We only have a proof in the plane with several restrictions, now on the sphere I would like to have an example without any restrictions (this is what I call conjecture), similarly to the 24 vertex graph in the plane.

  21. I am following this progress as a not-graph-theory-expert, and find it quite fascinating. I enjoy very much reading the overviews in the thread, which I can follow (or which motivates me to look into certain concepts). There has not been a new overview since septmber. Is one planned at some point? I am not really able to follow the progress on a big picture, for instance – what is the smallest graph that is not 4-colorable? What are the understandings of these sort of graphs? What is the property that makes it 4-colorable? Is the progress of this polymath large enough to merit a publication at some point? Thank you so much for doing the polymath, which allows others (like me) to follow live research 🙂

    Reply

  22. Well, I realized algorithm of Bellitto et al. for calculation of fractional chromatic number (FCN). I used both CPLEX and Gurobi (integer) linear program solvers, but trial version of Gurobi gives more possibilities (2000 variables and 2000 constraints). Both solvers are much faster than Mathematica solver (more than 100 times even for relatively small graphs with about 200 vertices), but even so they take too long time to calculate FCN of large graphs (more than 500 vertices). For example, I needed about 3 weeks intermittently (126 hours of pure time) to get FCN of Bellitto’s graph (607 vertices, 3390 edges). Btw, obtained FCN value \chi_f \approx 3.899389 is slightly different from result of Bellitto et al. \chi_f \approx 3.8992.

    Now my FCN record is \chi_f \approx 3.927329. The corresponding graph has 649 vertices, 3924 edges, 1020 spindles and vertex degree in range from 8 to 30.

    The pictures of graphs are shown below (numbers from top to bottom are vertex number, vertex weight divided by 10000 and orbit number).
    Vertex coordinates are available here:
    https://www.dropbox.com/s/50qhqx3oq2d5vfm/g607.vtx?dl=0
    https://www.dropbox.com/s/5sbkbizym1lu98o/g649a.vtx?dl=0

    It is always possible to get a graph with higher FCN value, the problem is to calculate FCN. The computation time increases roughly 10 times for every 100 additional vertices. It also depends on “niceness” of graph, but I still don’t know what makes the graph nice. The next problem is restrictions of trial versions of solvers. Maximum order of the graph is about 650…700 for trial version of Gurobi.

    Bellitto’s graph:

    My graph:

    Reply

    1. These are terrific findings Jaan – many thanks! Can your graph be described as a Minkowski sum (or some other nice combination) of simpler graphs? And what is its FCN as an exact fraction?

      It seems you are mighty close to being able to test Marijn’s smallest 5-chromatic graph. Do you think it is within reach?

      I think we still need to think about a different question too, namely whether there is a UD graph that has CN-FCN greater than 1 (or even equal to 1). As far as I know, nothing has been found that beats the case of increasingly large odd cycles, for which CN=3 and FCN asymptotically approaches 2 from above. Do you have any insights?

      Reply

    2. Yes, the background graph contains Minkowski sums, but the resulting graph is a mix from many graphs, so it is not so easy to get a formula. Exact fraction number is not available, it should contain large integers. The maximum graph with exact fraction I’ve found has \chi_f =27/7 \approx 3.85714.

      I tried to process Marijn’s 553-vertex graph with no success. The progress is very slow to see the end.

      I think here is the answer to your CN-FCN question (or not?):
      https://dustingmixon.wordpress.com/2018/09/14/polymath16-eleventh-thread-chromatic-numbers-of-planar-sets/#comment-6731

      Reply

      1. Thanks! Somehow I had missed your CN-FCN posts. Yeah, I guess it makes sense that a triangle-free graph would typically have a FCN less than 3 regardless of its CN. It might be interesting to look at O’Donnell’s 4-chromatic graphs of larger girth to see whether the FCN falls further.

      2. I can calculate FCN of any not very large graph. Bit I need vertex coordinates or vertex connections list. Could you provide it? I remember I did mistakes for some of O’Donnell’s graphs.

  23. A question related to FCN but perhaps conceptually simpler is whether a UD graph can have no independent vertex set consisting of more than 1/4 of its vertices. This seems to be verrry hard to find, but I suspect that that’s because we have not been trying to construct 5-chromatic graphs with a minimum rarest-colour vertex set greater than 1. I wonder whether we should try to find graphs with a bigger such set and see whether we can push the max-independent-set proportion below 1/4. Thoughts?

    Reply

  24. I expanded Lemma 39 and added Lemma 40 in the wiki article about the probabilistic formulation. These together give a lower bound for all p_d’s except for some neighbourhood of 1 (from roughly 0.62 to 1.401 if we also include the bounds in the notes). I also included these bounds in the table, but only the best ones for each d. The details of the calculations are omitted, some of them were made in WolframAlpha Pro.

    I also made two observations about this kind of proofs:
    1. If in a graph associated with a set of five points we fix which edges have length 1 and which ones have length d such that it gives us a lower bound for $p_d$, then this graph cannot be realized both for d \le \frac{1}{2} and for d \ge 2 (at least with the present upper bounds).

    Proof: These point sets only work if there are at least 8 segments from \lbrace 1,d \rbrace (if there would be only 7 such segments, the sum of the known upper bounds for the p‘s of the remaining edges would be at least 1). So there are at least 24 such triangle-side pairs, where the side is of length 1 or of length d (there are 3 possible triangles for all such segment), so at least 4 triangles which have all of their side-lengths as one of these two (otherwise there could only be at most 7\cdot 2+3\cdot 3=23 such pairs). But with going through the cases which only include equilateral triangles for these four (3 unit-length equilateral triangles and one d length, 2 unit-length and 2 d-length, …) we can easily see that this is impossible. So there is a triangle with side-lengths 1,1,d or 1,d,d, which implies the statement.

    2. Similarly to the 5 point case, we could also use this method for larger point sets but if we only use the number of monochromatic edges, but not their location, then we can see that there are only finitely many such point sets which can give us lower bounds this way (because of the upper bound for the edge number of unit distance graphs). From this, it concludes that some small neighbourhood of 1 cannot be covered if we follow this method strictly (at least as of the current upper bounds). But the location of the monochromatic edges isn’t arbitrary (they are forming 4 cliques), so if we use this too, there might be an infinite set of graphs which covers everything but 1. I might write something more detailed about this later.

    Reply

  25. My last FCN record is \chi_f \approx 3.952022. The corresponding graph has 655 vertices, 4068 edges, 1974 cliques, 1224 spindles (shown below).
    I also got 625-vertex 5-chromatic graph with \chi_f \approx 3.87032. It contains large (469-vertex) and small (157-vertex) subgraphs, connected via zero-weight vertices of large subgraph, so small subgraph does not affect FCN value. I think the same is true for Maijn’s 5-chromatic graphs too.

    Vertex coordinates are available here:
    https://www.dropbox.com/s/9jvu56xzbyykdci/g655.vtx?dl=0
    https://www.dropbox.com/s/57x3aeubbheahz7/g625.vtx?dl=0
    https://www.dropbox.com/s/xp7b43bnnrsqz0c/g469.vtx?dl=0

    655-vertex 4-chromatic graph:

    625-vertex 5-chromatic graph:

    469-vertex 4-chromatic subgraph:

    Reply

  26. A slightly related question in connection with Michael Burt decades project regarding regular “networks” in R^3. https://gilkalai.wordpress.com/2017/10/01/the-world-of-michael-burt-when-architecture-mathematics-and-art-meet/
    Michael studies vertex transitive infinite unit distance graphs in R^3 and he tries to classify them and study some of their parameters. In various cases he identifies dual networks and he even constructed 6 case where the network is self-dual. I wonder if there is some literature on infinite unit distance graphs in space with various regularity property.

    Reply

  27. Since the 11th thread has now 97 comments and the project deadline is one month from now, maybe it could be a good idea to prepare a new post and start a new thread.

    Reply

  28. With Tamas Hubai we have managed to come up with, unfortunately not an answer, but with the following two very nice question.

    What is the chromatic number of a typical large sphere?
    How many edges can a unit distance graph have?

    The problem needs a more detailed explanation. Our goal is to color all the points of a sphere in 3-dimension, i.e., a surface, such that points at unit distance receive different colors. It makes no difference whether the distance is measured on the surface or in 3-dim (I prefer the latter def), as we suppose that the radius of the sphere is typical, i.e., not special in the sense that there are no ‘accidental’ unit distances. This means that it behaves in a way like a free group.

    There seems to be surprisingly little known on the topic. There are some papers about small radius spheres, and many about spheres in d-dimensions, which study the chromatic number as a function of d, but nothing about this specific question which seems so related to the planar case (except that in the plane we do have ‘accidental’ unit distances).

    One can of course realize some Laman graphs, and with some spindling add a few extra unit edges to get 2n+clog n edges on n vertices, but we couldn’t do any better. If this was optimal, the chromatic number of typical spheres would be at most 5, which sounds implausible. (Btw, we couldn’t even prove an upper bound of 7 for all spheres.)

    Reply

    1. Hi Domotor – many thanks. Your “btw” is not remotely so! – it is extremely interesting. How and in what circumstances does the proof of an upper bound of 7 break down?

      Reply

      1. Initially I’m wondering about the range of radii that allow a 7-colouring of a buckyball, i.e. a truncated icosahedron and its extensions. I haven’t put pen to paper, but I feel that surely they must plug the gap between the 6-colorable dodecahedron and the plane. Are the pentagons more problematic than I’m visualising?

      2. The problem is that there’s no polyhedron that has only hexagons (unlike in the plane), it must have some pentagons too (see Goldberg polyhedra), around which it is easy to check that there’s no 7 coloring. I would expect that with some trickier tiling one might get a 7-coloring though, just we couldn’t find it. So I wrote ‘btw’ because we’ve found the other part of the question more interesting.

      3. Thanks. Yeah, my intuition was just that if we start with Goldberg polyhedra and we mess with the sizes of the tiles, making use of the flexibility inherent in the standard 7-coloring of the hexagonal tiling of the plane, it is somehow kinda gonna be possible to get something where the 7-coloring becomes possible. But you can tell from my wording that I was just winging it!

        I guess the place to start is to seek a radius above which 7-colouring is always possible. I havent’t done the check that a Goldberg polyhedron with all edges equal is not 7-colorable, but I’ll take your word for that – but then if we look at where a 7-colouring fails, we may see how it could be rescued by changes of size and shape in the vicinity of the pentagons, and then how those changes can be absorbed by the more pentagon-distant hexagons. Then, if that works, the task becomes to reduce the radius using increasingly creative shapes.

      4. So the easy-to-check claim is that if one puts hexagons around the pentagon in the ‘natural way’ (as in a Goldberg polyhedron), then it won’t be 7-colorable IF we consider boundaries to be bichromatic. Some trickier tiles could possibly help.

      5. Thanks again. Yeah, I’m seeing that now. If we give a pentagon colour 1 and its neighbours colours 2 through 6, we can then colour at most three of the ten hexagons in the next ring with colour 7, and at most one with colours 2 through 6, and of course none with 1. Looks like an 8-colouring has no problems though.

        Well, so we have a new question that we didn’t previously know we had! How large a sphere can we 7-colour? Presumably we should be looking at unscaleable tilings to get the best answer.

      6. I wish I had more time right now to examine this rigorously, but I have tentatively convinced myself that one can 7-colour a large sphere by placing copies of Philip’s 6-coloured disk (possibly with shape changes such as the version discovered by Jaan) at the 12 required places and then filling in the rest with hexagons in the natural way. I’m not 100% sure how the first ring of hexagons fits, but since we can use seven colours for the disks I feel fairly sure that we have enough flexibility. What do you think?

      8. Yes, that’s the one I meant – and Jaan’s refinement of it is here:

        https://dustingmixon.wordpress.com/2018/09/14/polymath16-eleventh-thread-chromatic-numbers-of-planar-sets/#comment-5989

        I think the best approach is to look for unscaleable tilings (i.e. ones whose boundaries are not bichromatic because the diameters and separations are both 1) from the start, since we already know so many other situations where that gives more options. We know from de Bruijn-Erdos that we can always find a colouring of the boundaries that works.

      10. Maybe I’m misunderstanding it. I thought that the conversion of the original CNP question into a finite-graph question was equivalent to this – in the same way that if we could push the Pritikin approach to arbitrarily small seventh-coloured tiles we would have that CNP>=6 – and I’m presuming that the same applies on a sphere. Apologies if I am talking nonsense!

    3. Also, whatever graph can be realized as a unit-distance graph on every large radius sphere, can also be realized on the plane by taking the limit. So I propose to call these generic unit-distance graphs (GUDG) and study the same questions for them as for UDG. Can we make a 5-chromatic GUDG? At least with a bichromatic origin? Can we get a better lower bound on the number of edges than n\log^*n?

      Reply

  29. Hey Domotor – another question (since we seem to be coming to the point of tying ends together): did you and Tamas get anywhere with cuboctahedra?

    Reply

    1. No, we couldn’t get anything on the unit sphere, mainly because there weren’t enough ‘accidental’ edges, that’s how this new question about the general sphere arose.

      Reply
  30. Pingback: Polymath16, twelfth thread: Year in review and future plans – Short, Fat Matrices

  31. Wow, I see life still here.

    I have some progress in FCN. My last FCN record is \chi_f \approx 3.961959.

    Here is a link to an interesting article about multicoloring: J. Grytczuk et al. “Fractional and j-fold coloring of the plane”, https://link.springer.com/article/10.1007/s00454-016-9769-3.
    It helps to better understand what is the fractional chromatic number and gives upper bounds for some b-fold chromatic numbers: \chi_2 \le 12, \chi_3 \le 16, \chi_4 \le 24, \chi_5 \le 32, \chi_6 \le 32, \chi_7 \le 37, \chi_8 \le 45, \chi_10 \le 55.
    Multicoloring (or a:b-coloring, or b-fold coloring, BCN) is an extension of the concept of vertex coloring in the case when each vertex is colored in some fixed number b of colors. In this case, the usual chromatic number (CN) corresponds to \chi = \chi_1, fractional chromatic number (FCN) corresponds to \chi_f=\lim_{b \rightarrow \infty} \frac{\chi_b}{b}.

    I’ve found slightly better upper bounds for some small b values. BCN could be interesting because it is possible to calculate it by SAT.
    As a first approximation (taking into account known results and inequality \chi_b \ge b \cdot \chi_f ) the following bounds for BCN of the plane are obtained:
    5 \le \chi_1 \le 7,
    8 \le \chi_2 \le 11,
    12 \le \chi_3 \le 16,
    16 \le \chi_4 \le 21,
    20 \le \chi_5 \le 26,
    24 \le \chi_6 \le 31,
    28 \le \chi_7 \le 36,
    36 \le \chi_9 \le 43,
    119 \le \chi_30 \le 143,
    143 \le \chi_36 \le 169.

    I have not worked on this task for a long time and I believe that some bounds can be improved rather quickly. It is interesting that to achieve some better bounds is not enough quite a bit. For example for b=4 the distance between the tiles should be only 0.64% larger to get upper bound \chi_4 \le 20, for b=6 it lacks only 0.1% to get \chi_6 \le 29.
    Also, I have a suspicion that my SAT-formulation is inefficient and not compact (if I have not made any mistakes at all). The number of clauses and computation time increase dramatically with an increase in the colors number \chi_b. I tested with SAT/UNSAT-programs (glucose and palsat) some small set of graphs and got the following results: \chi_2 \le 8, \chi_3 \le 11, \chi_4 \le 15, \chi_5 \le 18, \chi_6 \le 21. The ratio \frac{\chi_b}{b} does not exceed 4 for successfully tested graphs with \chi_f \gt 3.96 and \chi = 5. For graphs of the order of 1000 or more, the computation time exceeds several hours even for \chi_2, so I interrupted the calculations.

    Reply

    1. I already forgot the subtleties of syntax of tex. Corrupted formulas should be read like this: \chi_{10} \le 55, 119 \le \chi_{30} \le 143, 143 \le \chi_{36} \le 169, \chi_f > 3.96.

      Reply

    2. I see some practical motivations in that paper too. I feel I should work myself into that some time, but for the time being this stuff still goes over my head.

      Also you might want to take a look at the latest and last thread, as this Polymath is coming to an end in 2 weeks, hence the burst of final activity as people look to wrap their stuff up a little: https://dustingmixon.wordpress.com/2019/03/23/polymath16-twelfth-thread-year-in-review-and-future-plans

      Reply
  32. Pingback: 6-colourings of subsets of the plane | cp4space

Leave a Reply

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

Gravatar
WordPress.com Logo

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

Facebook photo

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

Cancel

Connecting to %s