Polymath16, eleventh thread: Chromatic numbers of planar sets

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.

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

1. ag24ag24 says:

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

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?

1. Jaan Parts says:

Aubrey, could you show your almost fine 36-tiles 6-colored sphere tessellation?

1. ag24ag24 says:

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. Jaan Parts says:

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. Jaan Parts says:

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

4. ag24ag24 says:

Sorry. I meant the tessellation in:

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. Jaan Parts says:

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.

6. ag24ag24 says:

Exactly right. It is really annoying that it doesn’t quite work!

2. Jaan Parts says:

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.)

3. test says:

4. Jaan Parts says:

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.

1. Jaan Parts says:

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).

1. Jaan Parts says:

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?

2. Tom Sirgedas says:

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.

2. Jaan Parts says:

Example of tessellation with $4^6:3$-coloring, 7th color density 1/9 and rational coloring number $k_r=6\frac34$ is shown below.

1. ag24ag24 says:

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.

3. Jaan Parts says:

Ops, correction is needed.

1. ag24ag24 says:

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. Jaan Parts says:

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.

3. ag24ag24 says:

First, can you make a proper picture of your dot-dash ideas? I couldn’t work them out.

4. Jaan Parts says:

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;)

5. ag24ag24 says:

I think it’s OK!

6. Jaan Parts says:

“Dash-dot” tessellation with $5^6:6$-coloring and 7th color density 1/6.

7. Jaan Parts says:

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

4. Jaan Parts says:

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).

5. Jaan Parts says:

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:

1. Tom Sirgedas says:

Seems like it’s a warped version of Pritkin’s pattern

5. Jaan Parts says:

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.

1. ag24ag24 says:

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?

1. Philip Gibbs says:

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

6. Jaan Parts says:

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$.

1. Jaan Parts says:

There is a lot of hidden pentagons here in fact. One can think about “pentagonal grid”. Could we spindle it?

1. ag24ag24 says:

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).

7. ag24ag24 says:

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!

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.

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. 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.)

3. Jaan Parts says:

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

8. ag24ag24 says:

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

9. ag24ag24 says:

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?

1. ag24ag24 says:

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.

1. ag24ag24 says:

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. Jaan Parts says:

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

3. ag24ag24 says:

Thanks Jaan – but, how did you determine that? Did you find an explicit weighting?

10. Jaan Parts says:

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$?

1. Jaan Parts says:

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$.

2. Jaan Parts says:

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.

3. Jaan Parts says:

Obviously, the answer to my question should be yes, FCN can only grow.

11. Jaan Parts says:

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)?

1. Jaan Parts says:

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$?

2. Jaan Parts says:

Is SAT-issue harder than UNSAT (in graph coloring)?

1. Marijn Heule says:

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. Jaan Parts says:

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. Marijn Heule says:

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. Jaan Parts says:

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. Marijn Heule says:

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. Jaan Parts says:

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.

12. 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.

1. dsp says:

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$.

1. dsp says:

Sorry, the covering map should wrap around three times.

2. dsp says:

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.

13. ag24ag24 says:

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?

1. No, but I also see no reason why it should be harder and you’ve already find a 5-chromatic UD in the plane.

1. ag24ag24 says:

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. ag24ag24 says:

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?

4. Not straightaway, at least.

14. ag24ag24 says:

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?

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.

1. ag24ag24 says:

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. ag24ag24 says:

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. ag24ag24 says:

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).

4. Could you please remind me what these clamps are?

15. ag24ag24 says:

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.)

1. Thanks. Indeed it’s hard to see a way to get around the fact that it might be the clamp that becomes 6-colored.

16. 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?

1. ag24ag24 says:

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?

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.

17. K says:

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 🙂