Details

This Demonstration gives a set of replacement rules, which are maps from the pre-image of one tile to a replacement image consisting of exactly nine tiles arranged in a larger square. Rules are specified up to rotation by some multiple of , except when such a rotation would lead to contradictory definitions. Circled tiles in the third row are relatively unimportant with measure zero in a patch as . The circled tiles only appear in the system so that the path can take the form of a cycle, that is, a curve with the topology of a circle's perimeter.

Replacement images have some ambiguity because the tiles are blank but need a color to be well defined. There are many tiles to color, which implies a vast space of possibilities. If we color just the 10 rules that are not circled, we get

possibilities. This is clearly too many to analyze or search. Up to rotation and reflection, we have three distinct "turn" tiles and two distinct "through" tiles. If we color by symmetry, then the total number of possibilities reduces to

.

Again, a set of this size is clearly too large to search or analyze. Fortunately, not all of these possibilities will lead to a continuous path through the Sierpinski carpet, so the actual number of valid solutions is much smaller.

The one positive result presented here is exceedingly instructive because it uses a simple coloring scheme, where a tile at is either blue or red depending on the divisibility of the sum by 2. This color scheme can be created by applying the color-only replacement rule in this Demonstration. Pairs of input/output ports on each replacement image fall in one of eight locations around the perimeter. These eight locations divide naturally into left and right subsets of cardinality four. Then all red (blue) tiles have I/O ports from the right (left) subset. Restricting to just the red and blue tiles, wherever the path crosses between two tiles, the color of the tiles must alternate between red and blue. The even/odd coloring is guaranteed to satisfy this condition, so the path is a valid solution, that is, continuous at every level of recursion.

We could go to a coding system based on edge markings rather than colors, and assign to each tile edge touched by the path a parity number 0 or 1, which determines if it belongs to the left or right subset upon replacement. The interior of every replacement image has exactly six crossings to set, and we treat exterior crossings on all tiles alike. Assigning one of four possibilities to exterior crossings, we arrive at a much reduced count

.

About four billion rule systems should lead to a valid Hamiltonian cycle, but before enumeration and exploration, it is difficult to say just how many of these systems would be unique.

To get going on enumeration, a suggested first step is to make an atlas of all possible adjacencies in the coloring system. Alternatively, it may be better to draw a new set of tiles (with arrows along the edges?) that more closely follows the minimal coding scheme. In such a system, it may be possible to avoid the necessity of a complicated adjacency atlas.

References

[1] E. W. Weisstein. "Sierpiński Carpet" from MathWorld—A Wolfram Web Resource. mathworld.wolfram.com/SierpinskiCarpet.html (Wolfram MathWorld).

[2] E. W. Weisstein. "Sierpiński Carpet Graph" from MathWorld—A Wolfram Web Resource. mathworld.wolfram.com/SierpinskiCarpetGraph.html (Wolfram MathWorld).

[3] R. W. Fathauer, "Fractal Gaskets: Reptiles, Hamiltonian Cycles, and Spatial Development," in Bridges Finland: Mathematics, Music, Art, Architecture, Education, Culture (Bridges Finland 2016), Jyväskylä, Finland (E. Torrence, B. Torrence, C. H. Séquin, D. McKenna, K. Fenyvesi and R. Sarhangi, eds.), Phoenix: Tessellations Publishing, 2016 pp. 217–224. archive.bridgesmathart.org/2016/bridges2016-217.pdf.