Notes on Golden B, by David Green
Samples of the various colored tilings described below can be found at
http://eddie.mapinfo.com/MIDiscovery/discovery.asp?action=7&id=732&ps=0
You can use the zoom and pan tools to look closer at a given tiling;
there's also a "layer control" button to allow you to make different
stages of the tile decomposition process visible. The publication method
is functional though somewhat awkward -- intended really for GIS
applications, not tilings, which is why the zoom level at the bottom is
given in miles! I will improve this at some point if anyone is
interested.
----------------------------------
Start with a graph consisting of a unit square with two of the opposing
corners connected. This will be called "stage 2" of the graph. (Stage 0
is a point, stage 1 is a unit horizontal line -- it's simplest to start
with stage 2. It doesn't matter at this point which initial diagonal is
chosen.)
Each stage N+1 of the graph is composed from two copies of stage N. The
second copy should be reflected in the Y axis and translated Fib(N\2)
units downward in relation to the first copy. The two copies will
overlap by Fib(N\2-1)-1. [ N\2 denotes integer division by 2. Fib(0)=1,
Fib(1)=1, Fib(N)=Fib(N-1)+Fib(N-2). ]
[Unproved fact #1: The diagonal lines in the overlapping sections of the
copies will always match perfectly. A proof of this interesting fact is
left as an exercise for the reader -- because, while I'm reasonably sure
it is true, I can't exactly prove it.]
After the copy, reflection, and translation operations, rotate the
resulting larger graph 90 degrees clockwise to obtain stage N+1.
For even N, the stage-N graph will be a square of side Fib(N/2+1)-1. For
odd N, the graph will be a rectangle Fib((N+1)/2)-1 units wide, by
Fib((N-1)/2)-1 units tall.
Unproved fact #2: Any stage of the resulting graph is three-colorable,
and the solution is unique up to the choice of color. The "unique" part
is relatively easy: diagonal lines should never cross inside a unit
square, and every unit square has a diagonal in it, dividing it into two
triangles. If there is a solution, it can be easily obtained by
assigning three colors to any three nodes of a triangle inside any unit
square in the graph. This triangle will share two nodes with at least
one other triangle in the graph -- so the color of that triangle's third
node is forced. Assuming that a three-coloring exists at all, the
colorization then can be completed by induction -- all nodes' colors are
forced by the choice of colors for the first triangle. There's a proof
in there somewhere.
But proving that all stages of this pattern are actually three-colorable
seems more difficult. One approach might be to prove by inspection that
everything up to, say, stage 6 is three-colorable; then prove that the
overlapping sections of the graph will always match (U.F. #2); then note
that each stage N>6 is made up of two overlapping stage N-1 pieces, which
are already known to be three-colorable; and proceed by induction.
In some sense I think this is a good explanation of why this graph _is_
three-colorable: it just happened to start out being three-colorable --
and because of the recursive definition, if a 6x6 square is
three-colorable then all larger stages of graph must be.
------------------------------------------
But with Fibonnacci mixed up in the definition, I'm sure there are fifty
other ways of looking at the problem that all turn out to be the same
underneath.
For example, an interesting way of obtaining this graph is to start with
a single Golden-B (or "Golden Bee") tile, corresponding to stage 0 of the
graph. [See
http://www.meden.demon.co.uk/Fractals/golden.html
or page 553 of Grunbaum and Shepard's book _Tilings and Patterns_ for
more information about this tile.]
To produce each stage N+1 from stage N, cut each of the Fib(N-1) _larger_
copies of the tile into two similar small copies. At any stage, the
resulting tiling is uniquely three-colorable -- if you include the
additional requirement that all three colors must be used wherever four
tiles meet at a corner. [It may not be necessary to specify this as a
requirement; I haven't yet found a counterexample showing an alternate
valid three-coloring of one of these tilings, if this requirement is
relaxed -- but I'm worried that there may be one. At any rate, relaxing
this requirement makes it much harder to prove that the three-coloring is
unique.]
The graph described above can then be produced by replacing all tiles
with nodes, and drawing lines between each pair of neighboring tiles that
have the same color. (Each interior tile has eight "nearest neighbors";
note that they may not be actually adjacent). Alternatively, as I
recall, drawing lines between pairs of neighboring tiles whose colors do
_not_ match is equivalent to rotating all the unit-cell diagonals in the
graph by 90 degrees.
-----------------------
Tangent: another three-colorable tiling using the Golden B tile is
obtained by cutting every tile in each stage into its two similar
sub-tiles (not just the larger tiles in each stage). Stage N of this
tiling has 2^N tiles instead of Fib(N), with tiles of N different sizes.
With 0, 1, and 2 as possible colors, if the color of the _larger_
sub-tile is incremented (mod 3) after every decomposition, a unique
three-coloring is the result -- there is definitely no need for
additional restrictions in this case.
Another tangent: this kind of recursive coloring rule also works on
(certain) other, apparently unrelated aperiodic tilings. In particular,
two different dissections of Penrose triangles (formed by cutting the
well-known Penrose rhombs in half -- the long way for the fat rhomb, the
short way for the skinny one) can be three-colored in this way. The only
difference is that the color of the _smaller_ sub-tile is cycled at each
stage, with the larger sub-tile's color remaining the same.
------------------------
As I mentioned in my last email, I just recently figured out how to
generate the above graph, and thus the associated three-color pattern,
very simply and directly from the "Golden String" sequence
S(0) = "0"
S(1) = "1"
S(N) = S(N-1) & S(N-2)
[There's really only one color pattern in each direction -- e.g. if a
tile (or node) at the top of a column or the beginning of a row is a
given color, any column or row starting with that color will match the
colors of the original column or row, all the way to the end. Columns
and rows starting with other colors can be duplicated by applying the
same color shift (modulo 3) to the original column or row.]
But I'm still cleaning up some of the details. I'll write them up in
more detail in a separate email if you're interested.