2
$\begingroup$

In 2 dimensions, the Moser spindle is a set of 7 points that makes a unit-distance graph with chromatic number 4.

In 3 dimensions, the Raiskii spindle and the Nechushtan spindle provide sets of points whose unit-distance graphs have chromatic number 5. Nechushtan claimed that rotations of his point set could provide a chromatic 6 unit distance graph, but did not provide a specific set of points or rotations.

I've seen claims of a chromatic-6 set of points from 59 to 80 points, but the point sets never seem to be provided. For example.

Could someone provide a set of 100 or less points so that the graph of unit-distance edges between points has chromatic number 6? Is there a lower bound for the number of points needed?

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

It's possible to create a 6-chromatic unit-distance graph in R^3 with just 47 vertices and 146 edges. The way to construct it is described in an article in Geombinatorics.(The january 2022 issue) The article leaves it to the reader to calculate most of the coordinates. I can do it and give you a list of coordinates if you are still interested.

I have calculated the coordinates and i hope that there are no mistakes. This is just one of many ways to make a 6 chromatic unit distance graph with 47 vertices and 146 edges.

The 47 coordinates for the vertices: A: (5/(3sqrt(2)), 0, 0), B: (0, 5/(3sqrt(2)), 0), C: (0, 0, 5/(3sqrt(2))), D: (2sqrt(2)/9, 2sqrt(2)/9, -5/(9sqrt(2))), E: (2sqrt(2)/9, -5/(9sqrt(2)) ,2sqrt(2)/9), F: (-5/(9sqrt(2)), 2sqrt(2)/9, 2sqrt(2)/9), G: (2sqrt(2)/3, 2sqrt(2)/3, 1/(3sqrt(2))), H: (2sqrt(2)/3, 1/(3sqrt(2)), 2sqrt(2)/3), I: (1/(3sqrt(2)), 2sqrt(2)/3, 2sqrt(2)/3), J: (1/(3sqrt(2)),1/(3sqrt(2)),1/(3sqrt(2))), K: (7/(9sqrt(2)), 7/(9sqrt(2)), 7/(9sqrt(2))) Q_1: ((533-2sqrt(2289118))/(3915sqrt(2)), (5084-2sqrt(2289118))/(3915sqrt(2)), (908-2sqrt(2289118))/(3915sqrt(2)))=(-0.450266505825, 0.371711262037, -0.382535971229), Q_2: (0.485385127230, 0.685868510755, -0.221721653957), Q_3: (0.306581088586, -0.281632513290, -0.400525692600), Q_4: (0.755545030725, 0.462841753533, 0.714906709967), Q_5: (0.576740992081, -0.504659270512, 0.536102671323), Q_6: (-0.188803313430, 0.724698946143, 0.515816239150), Q_7: (-0.385092822141, -0.337415210379, 0.319526730439), Q_8: (0.161335973550, -0.158737933544, 0.204461522914), Q_9: (0.268223462939, 0.419625710956, 0.311349012303) R_1: (-(-10528 + 25 sqrt(55729) + 45 sqrt(4037 + 256 sqrt(55729)))/(12528 sqrt(2)), (10528 - 25 sqrt(55729) + 45 sqrt(4037 + 256 sqrt(55729)))/(12528 sqrt(2)), (1255/783 - (5 sqrt(55729))/6264)/sqrt(2))=(-0.383792334607, 0.906023245781, 1.000114771738), R_2: (0.282999993708, 1.566470856363, 0.654865666632), R_3: (0.593042080603, 0.757305006114, 1.153989429985), R_4: (0.701837202788, 1.211418717211, -0.180905456807), R_5: (1.011879289684, 0.402252866962, 0.318218306547), R_6: (-0.260708181565, 1.023704043675, 0.014720677440), R_7: (0.079653307907, 0.135408855180, 0.562654376464), R_8: (0.454775490129, 0.585988044449, 0.559227628325), R_9: (0.269435044105, 1.069700307820, 0.260855810978) U_1: (0.906023245781, 1.000114771738, -0.383792334607), U_2: (1.566470856363, 0.654865666632, 0.282999993708), U_3: (0.757305006114, 1.153989429985, 0.593042080603), U_4: (1.211418717211, -0.180905456807, 0.701837202788), U_5: (0.402252866962, 0.318218306547, 1.011879289684), U_6: (1.023704043675, 0.014720677440, -0.260708181565), U_7: (0.135408855180, 0.562654376464, 0.079653307907), U_8: (0.585988044449, 0.559227628325, 0.454775490129), U_9: (1.069700307820, 0.260855810978, 0.269435044105) T_1: (1.000114771738, -0.383792334607, 0.906023245781), T_2: (0.654865666632, 0.282999993708, 1.566470856363), T_3: (1.153989429985, 0.593042080603, 0.757305006114), T_4: (-0.180905456807, 0.701837202788, 1.211418717211), T_5: (0.318218306547, 1.011879289684, 0.402252866962), T_6: (0.014720677440, -0.260708181565, 1.023704043675), T_7: (0.562654376464, 0.079653307907, 0.135408855180), T_8: (0.559227628325, 0.454775490129, 0.585988044449), T_9: (0.260855810978, 0.269435044105, 1.069700307820)

The 146 edges: {{D,E},{D,F},{E,F},{G,H},{G,I},{H,I},{A,D},{A,E},{A,G},{A,H},{B,D},{B,F},{B,G},{B,I},{C,E},{C,F},{C,H},{C,I},{A,J},{B,J},{C,J},{A,K},{B,K},{C,K},{D,K},{E,K},{F,K},{G,J},{H,J},{I,J},{Q_1,Q_2},{Q_1,Q_3},{Q_1,Q_6},{Q_1,Q_7},{Q_1,Q_8},{Q_1,Q_9},{Q_2,Q_3},{Q_2,Q_4},{Q_2,Q_6},{Q_2,Q_8},{Q_3,Q_5},{Q_3,Q_7},{Q_3,Q_9},{Q_4,Q_5},{Q_4,Q_6},{Q_4,Q_8},{Q_5,Q_7},{Q_5,Q_9},{Q_6,Q_8},{Q_7,Q_9},{Q_1,B},{Q_2,A},{Q_3,A},{Q_4,C},{Q_5,C},{Q_6,C},{Q_7,C},{Q_8,C},{Q_9,C},{R_1,R_2},{R_1,R_3},{R_1,R_6},{R_1,R_7},{R_1,R_8},{R_1,R_9},{R_2,R_3},{R_2,R_4},{R_2,R_6},{R_2,R_8},{R_3,R_5},{R_3,R_7},{R_3,R_9},{R_4,R_5},{R_4,R_6},{R_4,R_8},{R_5,R_7},{R_5,R_9},{R_6,R_8},{R_7,R_9},{R_1,C},{R_2,G},{R_3,G},{R_4,D},{R_5,D},{R_6,D},{R_7,D},{R_8,D},{R_9,D},{U_1,U_2},{U_1,U_3},{U_1,U_6},{U_1,U_7},{U_1,U_8},{U_1,U_9},{U_2,U_3},{U_2,U_4},{U_2,U_6},{U_2,U_8},{U_3,U_5},{U_3,U_7},{U_3,U_9},{U_4,U_5},{U_4,U_6},{U_4,U_8},{U_5,U_7},{U_5,U_9},{U_6,U_8},{U_7,U_9},{U_1,B},{U_2,H},{U_3,H},{U_4,E},{U_5,E},{U_6,E},{U_7,E},{U_8,E},{U_9,E},{T_1,T_2},{T_1,T_3},{T_1,T_6},{T_1,T_7},{T_1,T_8},{T_1,T_9},{T_2,T_3},{T_2,T_4},{T_2,T_6},{T_2,T_8},{T_3,T_5},{T_3,T_7},{T_3,T_9},{T_4,T_5},{T_4,T_6},{T_4,T_8},{T_5,T_7},{T_5,T_9},{T_6,T_8},{T_7,T_9},{T_1,A},{T_2,I},{T_3,I},{T_4,F},{T_5,F},{T_6,F},{T_7,F},{T_8,F},{T_9,F}}

$\endgroup$
8
  • 1
    $\begingroup$ In the weekend I have the time to calculate the coordinates and then I will post it here. $\endgroup$
    – Asger Haugstrup
    Commented Nov 9, 2022 at 19:25
  • 1
    $\begingroup$ You are right. There should be a minus sign there. I have changed it now, $\endgroup$
    – Asger Haugstrup
    Commented Nov 14, 2022 at 20:23
  • 1
    $\begingroup$ True. It's this A-K shape with four Nechushtan-spindles attached. Take a tetrahedon and glue 3 tetrahedrons to three of the faces and then you have 7-vertex structure. Then do a reflexion in the plane containing the 3 vertices that does not belong to the central tetrahedron and you get this 7+7-3 =11 vertex structure. I don't think it has a name by it'self. $\endgroup$
    – Asger Haugstrup
    Commented Nov 15, 2022 at 4:54
  • 1
    $\begingroup$ The A-K shape has a couple of important properties: 1. It contains 11 vertices and due to the pigeonhole-principle it has to contain a monochromatic triple if the vertices are colored with 5 colors or less. 2. With a proper coloring of the graph there are only 4 possible ways a monochromatic triple can appear in it. 3. The possible monochomatic triples all creates sufficiently 'nice' triangles that can be attached to Nechushtan-spindles in such a way that if the triangle is monochromatic then together with the Nechushstan spindle it needs at least 6 colors. $\endgroup$
    – Asger Haugstrup
    Commented Nov 15, 2022 at 15:37
  • 1
    $\begingroup$ You can call the A-K shape for the scaffold of the spindle/graph. This is the terminology Aubrey de Grey is using. $\endgroup$
    – Asger Haugstrup
    Commented Nov 18, 2022 at 7:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .