
Re: cotpi 69  Black and white plane
Posted:
Oct 6, 2013 8:15 AM



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.
David Bernier
 Let us all be paranoid. More so than no such agence, Bolon Yokte K'uh willing.

