
Re: cotpi 69  Black and white plane
Posted:
Oct 6, 2013 9:56 AM


On 10/06/2013 09:19 AM, David Bernier wrote: > On 10/06/2013 08:15 AM, David Bernier wrote: >> On 10/06/2013 05:52 AM, David Bernier wrote: >>> On 10/02/2013 10:29 PM, Mike Terry wrote: >>>> "quasi" <quasi@null.set> wrote in message >>>> news:v9vo49lvr7j4ns7i82s869ou749lgdmrup@4ax.com... >>>>> Pubkeybreaker wrote: >>>>>> Susam Pal wrote: >>>>>>> >>>>>>> How can you construct a plane where every point is coloured >>>>>>> either black or white such that two points of the same colour >>>>>>> are never a unit distance apart? >> [snip] >>>>>> It does not seem possible. Take any point. Suppose it is >>>>>> white. It is the center of a circle (of radius 1). All points >>>>>> on that circle must then be black. But given any point on >>>>>> that circle there is another point on the circle at distance 1. >>>>>> Both points are the same color. >>>>>> >>>>>> Unless, of course, I am being completely stupid. >>>>> >>>>> No, your proof is fine. >>>>> >>>>> quasi >>>> >>>> The question was asked here a few years ago whether the plane can be >>>> coloured along the lines above but using three colours. The answer is no, >>>> and the proof is similar but less obvious... >>> [...] >>> >>> There is a webpage called "Chromatic Number of the Plane" by >>> Alexander Bogomolny that briefly discusses the question of >>> the minimum number of colours needed. >>> >>> The relevant definition, copied from there, is: >>> ``The smallest number of colors needed in a coloring of the plane to >>> ensure that no monochromatic pair is at the unit distance apart is >>> called the chromatic number Chi of the plane." >>> >>> Ref.: >>> < http://www.cuttheknot.org/proofs/ChromaticNumber.shtml > . >>> >>> Two or three colours won't do, from which we see that Chi >= 4. >>> A 7colouring of a regularhexagon tiling of the plane shows >>> that seven colours will do, from which we see that Chi <= 7. >> >> [snip] >> >>> The Chi question, according to the Wikipedia article above, is >>> also known as the Hadwiger?Nelson problem : >>> >>> < http://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem > >>> >>> The "Moser spindle" unitdistance graph shows that Chi >=4 : >>> < http://en.wikipedia.org/wiki/Moser_spindle > >>> >>> There are only 7 vertices, so it's easy to describe: >>> >>> Let A be a point in the plane at (0, 0). >>> Let B be the point (1,0). >>> Let C be the point in Quadrant I which is at unit distance >>> from both A and B. So C has coordinates: (cos pi/3, sin pi/3). >>> >>> A is one of the two points which are at unit distance from >>> both B and C. Let us call the second point D. >>> >>> Let E be an as yet undetermined point on the circle of >>> radius 1 centered at A. >>> >>> Let F be determined, relative to A and E, by requiring >>> that the unitsegment AF is obtained by rotating the >>> unitsegment AE through pi/3 [60 degrees] counterclockwise. >>> >>> Then, E and F shall be one unit distance apart. >>> >>> A is one of the two points at unit distance from both E and >>> F. Let G be the second point at unit distance from both E and >>> F. >>> >>> We have the unitsided equilateral triangles: ABC, BCD, >>> AEF, EFG. >>> >>> Like ("suggested") in the figure in the top right box at: >>> http://en.wikipedia.org/wiki/Moser_spindle , >>> >>> with A being the highest point in the figure, >>> points D and G are the furthest from A, >>> and also the lowest in the drawing. >>> >>> The points called B, C, E, F are all at unit distance >>> from A . >>> >>> Then we require finally that D and G be a unit distance apart. >>> Then the line segments AD and AG have the same length. >>> We can fix G down to unique by asking that there be a >>> counterclockwise rotation through A of less than 180 degrees >>> that maps segment AD to segment AG. >>> >>> With a threecolouring, considering in turn >>> {A, B, C, D} and {A, E, F, G}, >>> one is forced to colour D the colour of A, and also >>> forced to colour G the colour of A. So D and G, although >>> unit distance apart, share the same colour (X). >>> >>> So the Moser spindle needs at least 4 colors. >>> >>> The Moser spindle is related by Wikipidia to be a Laman graph, >>> which have a type of rigidity property: >>> < http://en.wikipedia.org/wiki/Laman_graph > . >>> >>> After some thinking, I realized that the Moser spindle, as a rigid >>> figure in the plane consisting of 4 equilateral triangles of >>> unit length and 7 distinct vertices, is constructible by >>> ruler and compass ... >>> >>> Also, I tried that out experimentally. >>> >>> The wikipedia article on ruler and compass, >>> < http://en.wikipedia.org/wiki/Compassandstraightedge_construction > >>> >>> says that: >>> ``It is possible (according to the Mohr?Mascheroni theorem) to construct >>> anything with just a compass if it can be constructed with a ruler and >>> compass, provided that the given data and the data to be found consist >>> of discrete points (not lines or circles)." >>> >>> In the Moser spindle case, if we suppose A = (0, 0) and >>> B = (1, 0) as the starting point, >>> then it's easy to construct C by compass. >>> >>> Also, constructing D by compass is easy. Then G seems >>> easy also, which leaves E and F. >>> >>> So, I thought of writing a computer program to devise pseudorandom >>> compassonly constrcutions of finite number of points, with an aim >>> of getting "lots" of pairs of points at unit distance from each other. >> [snip] >> >> (aside: Erdos wrote that he was almost sure that Chi > 4, for >> the plane). >> >> I thought of a decision problem, related to "random graphs" >> with many pairs of points at unit distance from each other. >> >> Suppose I have a 50x50 matrix T with entries in {0, 1}. >> It's a given that T is symmetric, meaning T = T^t, and >> that the main diagonal of T is all zeros. >> >> === >> >> The decision problem for T is this: >> >> Do there exist 50 distinct points (x_1, y_1) ... (x_50, y_50) in >> R^2 such that >> >> T_{i, j} = 1 if and only if : (x_i  x_j)^2 + (y_i  y_j)^2 =1, >> valid for 1 <= i <= 50 and for 1 <= j <= 50 ? >> >> With '7' taking the place of '50' in a natural way, >> >> T is a 7x7 symmentic matrix with 0/1 entries, for example: >> >> T := >> [0 1 1 0 1 1 0] >> [1 0 1 1 0 0 0] >> [1 1 0 1 0 0 0] >> [0 1 1 0 0 0 1] >> [1 0 0 0 0 1 1] >> [1 0 0 0 1 0 1] >> [0 0 0 1 1 1 0] >> >> So, do there exist 7 distinct points (x_1, y_1), (x_2, y_2), (x_3, y_3), >> (x_4, y_4), (x_5, y_5), (x_6, y_6) and (x_7, y_7) >> in R^2 such that: >> >> for 1<= i, j <=7 : (x_i  x_j)^2 + (y_i  y_j)^2 = 1 if and only if >> T_{i, j} = 1 ? >> >> === >> >> I constrcuted the 7x7 matrix T based on the Moser spindle (that is, >> taking as points the vertices in the Moser spindle). >> >> So, unless my T is mistaken, the decision problem for the 7x7 matrix >> T above is that "Yes, it's doable". >> >> I note that all that can be "gleaned" from T_{i, j} being zero >> is that (x_i, y_i) and (x_j, y_j) _cannot_ be a distance 1 apart, >> which seems quite weak as a constraint ... >> >> >> In the context of searching for figures needing at least 4 colours >> (maybe at least 5 later on), one could change the offdiagonal >> '0's for just *, meaning "either 0 or 1". >> >> Then, the new T, T2 is: >> >> T2 := >> [0 1 1 * 1 1 *] >> [1 0 1 1 * * *] >> [1 1 0 1 * * *] >> [* 1 1 0 * * 1] >> [1 * * * 0 1 1] >> [1 * * * 1 0 1] >> [* * * 1 1 1 0] >> >> I believe there are 11 basic "distance 1" constraints above, at >> one per pair of unitdistance points. > [...] > > With 7 points and 2 real variables per point, we have > 14 real variables and 11 equations. The Moser spindle > has 3 degrees of freedom, with centroid counting for 2 > and the orientation counting for 1. > > So, with 50 points, we have 100 real variables > so it might be typically 1003 = 97 "distance 1" constraints. > I wonder if this is easy or hard, as a decision problem ...
Suppose we are looking for finite plane pointconfigurations that must use at least 4 colours. Suppose Q is such as configuration.
If Z is a point in the configuration Q, and Z has two or fewer points in Q at unitdistance from Z, then it seems to me harmless to delete the Point Z from the configuration, meaning that Q less Z would still need at least 4 colours.
But is it really true? and if so, how could one prove it?
Indeed, in the Moser spindle, with the seven points, we have in some order: 4, 3, 3, 3, 3, 3, 3 points at unitdistance [from A, B, C, D, E, F and G, respectively]. So always at least 3 points at distance 1 from some given point, in the case of the Moser spindle at least.
David Bernier
 Let us all be paranoid. More so than no such agence, Bolon Yokte K'uh willing.

