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.