# Graphs, Kites and Darts – Empires and SuperForce

We have been exploring properties of Penrose’s aperiodic tilings with kites and darts using Haskell.

Previously in Diagrams for Penrose tiles we implemented tools to draw finite tilings using Haskell diagrams. There we also noted that legal tilings are only correct tilings if they can be continued infinitely and are incorrect otherwise. In Graphs, Kites and Darts we introduced a graph representation for finite tilings (Tgraphs) which enabled us to implement operations that use neighbouring tile information. In particular we implemented a `force` operation to extend a Tgraph on any boundary edge where there is a unique choice for adding a tile.

In this note we find a limitation of `force`, show a way to improve on it (`superForce`), and introduce boundary coverings which are used to implement `superForce` and calculate empires.

## Properties of Tgraphs

A Tgraph is a collection of half-tile faces representing a legal tiling and a half-tile face is either an `LD` (left dart) , `RD` (right dart), `LK` (left kite), or `RK` (right kite) each with 3 vertices to form a triangle. Faces of the Tgraph which are not half-tile faces are considered external regions and those edges round the external regions are the boundary edges of the Tgraph. The half-tile faces in a Tgraph are required to be connected and locally tile-connected which means that there are exactly two boundary edges at any boundary vertex (no crossing boundaries).

As an example Tgraph we show `kingGraph` (the three darts and two kites round a king vertex), where

``````  kingGraph = makeTgraph
[LD (1,2,3),RD (1,11,2),LD (1,4,5),RD (1,3,4),LD (1,10,11)
,RD (1,9,10),LK (9,1,7),RK (9,7,8),RK (5,7,1),LK (5,6,7)
]``````

This is drawn in figure 1 using

``  hsep 1 [dashJVGraph kingGraph, drawGraph kingGraph]``

which shows vertex labels and dashed join edges (left) and without labels and join edges (right). (`hsep 1` provides a horizontal seperator of unit length.)

## Properties of forcing

We know there are at most two legal possibilities for adding a half-tile on a boundary edge of a Tgraph. If there are zero legal possibilities for adding a half-tile to some boundary edge, we have a stuck tiling/incorrect Tgraph.

Forcing deals with all cases where there is exactly one legal possibility for extending on a boundary edge. That means forcing either fails at some stage with a stuck Tgraph (indicating the starting Tgraph was incorrect) or it enlarges the starting Tgraph until every boundary edge has exactly two legal possibilities for adding a half-tile so a choice would need to be made to grow the Tgraph any further.

Figure 2 shows `force kingGraph` with `kingGraph` shown red.

If `g` is a correct Tgraph, then `force g` succeeds and the resulting Tgraph will be common to all infinite tilings that extend the finite tiling represented by `g`. However, we will see that `force g` is not a greatest lower bound of (infinite) tilings that extend `g`. Firstly, what is common to all extensions of `g` may not be a connected collection of tiles. This leads to the concept of empires which we discuss later. Secondly, even if we only consider the connected common region containing g, we will see that we need to go beyond `force g` to find this, leading to an operation we call `superForce`.

Our `empire` and `superForce` operations are implemented using boundary coverings which we introduce next.

## Boundary edge covering

Given a successfully forced Tgraph `fg`, a boundary edge covering of `fg` is a list of successfully forced extensions of `fg` such that

1. no boundary edge of `fg` remains on the boundary in each extension, and
2. the list takes into account all legal choices for extending on each boundary edge of `fg`.

[Technically this is a covering of the choices round the boundary, but each extension is also a cover of the boundary edges.] Figure 3 shows a boundary edge covering for a forced `kingGraph` (`force kingGraph` is shown red in each extension).

In practice, we do not need to explore both choices for every boundary edge of `fg`. When one choice is made, it may force choices for other boundary edges, reducing the number of boundary edges we need to consider further.

The main function is `boundaryECovering` working on a `BoundaryState` (which is a Tgraph with extra boundary information). It uses `covers` which works on a list of extensions each paired with the remaining set of the original boundary edges not yet covered. (Initially `covers` is given a singleton list with the starting boundary state and the full set of boundary edges to be covered.) For each extension in the list, if its uncovered set is empty, that extension is a completed cover. Otherwise `covers` replaces the extension with further extensions. It picks the (lowest numbered) boundary edge in the uncovered set, tries extending with a half-dart and with a half-kite on that edge, forcing in each case, then pairs each result with its set of remaining uncovered boundary edges before adding the resulting extensions back at the front of the list to be processed again. If one of the choices for a dart/kite leads to an incorrect tiling (a stuck tiling) when forced, that choice is dropped (provided the other choice succeeds). The final list returned consists of all the completed covers.

``````  boundaryECovering:: BoundaryState -> [BoundaryState]
boundaryECovering bs = covers [(bs, Set.fromList (boundary bs))]

covers:: [(BoundaryState, Set.Set Dedge)] -> [BoundaryState]
covers [] = []
covers ((bs,es):opens)
| Set.null es = bs:covers opens -- bs is complete
| otherwise   = covers (newcases ++ opens)
where (de,des) = Set.deleteFindMin es
newcases = fmap (\b -> (b, commonBdry des b))
(atLeastOne \$ tryDartAndKite bs de)``````

Here we have used

``````  type Try a = Either String a
tryDartAndKite:: BoundaryState -> Dedge -> [Try BoundaryState]
atLeastOne    :: [Try a] -> [a]``````

We frequently use `Try` as a type for results of partial functions where we need to continue computation if there is a failure. For example we have a version of `force` (called `tryForce`) that returns a `Try Tgraph` so it does not fail by raising an error, but returns a result indicating either an explicit failure situation or a successful result with a final forced Tgraph. The function `tryDartAndKite` tries adding an appropriate half-dart and half-kite on a given boundary edge, then uses `tryForceBoundary` (a variant of `tryForce` which works with boundary states) on each result and returns a list of `Try` results. The list of `Try` results is converted with `atLeastOne` which collects the successful results but will raise an error when there are no successful results.

## Boundary vertex covering

You may notice in figure 3 that the top right cover still has boundary vertices of `kingGraph` on the final boundary. We use a boundary vertex covering rather than a boundary edge covering if we want to exclude these cases. This involves picking a boundary edge that includes such a vertex and continuing the process of growing possible extensions until no boundary vertices of the original remain on the boundary.

## Empires

A partial example of an empire was shown in a 1977 article by Martin Gardner 1. The full empire of a finite tiling would consist of the common faces of all the infinite extensions of the tiling. This will include at least the force of the tiling but it is not obviously finite. Here we confine ourselves to the empire in finite local regions.

For example, we can calculate a local empire for a given Tgraph `g` by finding the common faces of all the extensions in a boundary vertex covering of `force g` (which we call `empire1 g`).

This requires an efficient way to compare Tgraphs. We have implemented guided intersection and guided union operations which, when given a common edge starting point for two Tgraphs, proceed to compare the Tgraphs face by face and produce an appropriate relabelling of the second Tgraph to match the first Tgraph only in the overlap where they agree. These operations may also use geometric positioning information to deal with cases where the overlap is not just a single connected region. From these we can return a union as a single Tgraph when it exists, and an intersection as a list of common faces. Since the (guided) intersection of Tgraphs (the common faces) may not be connected, we do not have a resulting Tgraph. However we can arbitrarily pick one of the argument Tgraphs and emphasise which are the common faces in this example Tgraph.

Figure 4 (left) shows `empire1 kingGraph` where the starting `kingGraph` is shown in red. The grey-filled faces are the common faces from a boundary vertex covering. We can see that these are not all connected and that the `force kingGraph` from figure 2 corresponds to the connected set of grey-filled faces around and including the `kingGraph` in figure 4.

We call this a level 1 empire because we only explored out as far as the first boundary covering. We could instead, find further boundary coverings for each of the extensions in a boundary covering. This grows larger extensions in which to find common faces. On the right of figure 4 is a level 2 empire (`empire2 kingGraph`) which finds the intersection of the combined boundary edge coverings of each extension in a boundary edge covering of `force kingGraph`. Obviously this process could be continued further but, in practice, it is too inefficient to go much further.

## SuperForce

We might hope that (when not discovering an incorrect tiling), `force g` produces the maximal connected component containing `g` of the common faces of all infinite extensions of `g`. This is true for the `kingGraph` as noted in figure 4. However, this is not the case in general.

The problem is that forcing will not discover if one of the two legal choices for extending a resulting boundary edge always leads to an incorrect Tgraph. In such a situation, the other choice would be common to all infinite extensions.

We can use a boundary edge covering to reveal such cases, leading us to a `superForce` operation. For example, figure 5 shows a boundary edge covering for the forced Tgraph shown in red.

This example is particularly interesting because in every case, the leftmost end of the red forced Tgraph has a dart immediately extending it. Why is there no case extending one of the leftmost two red edges with a half-kite? The fact that such cases are missing from the boundary edge covering suggests they are not possible. Indeed we can check this by adding a half-kite to one of the edges and trying to force. This leads to a failure showing that we have an incorrect tiling. Figure 6 illustrates the Tgraph at the point that it is discovered to be stuck (at the bottom left) by forcing.

Our `superForce` operation starts by forcing a Tgraph. After a successful force, it creates a boundary edge covering for the forced Tgraph and checks to see if there is any boundary edge of the forced Tgraph for which each cover has the same choice. If so, that choice is made to extend the forced Tgraph and the process is repeated by applying `superForce` to the result. Otherwise, just the result of forcing is returned.

Figure 7 shows a chain of examples (rockets) where `superForce` has been used. In each case, the starting Tgraph is shown red, the additional faces added by forcing are shown black, and any further extension produced by `superForce` is shown in blue.

## Coda

We still do not know if forcing decides that a Tgraph is correct/incorrect. Can we conclude that if `force g` succeeds then `g` (and `force g`) are correct? We found examples (rockets in figure 7) where force succeeds but one of the 2 legal choices for extending on a boundary edge leads to an incorrect Tgraph. If we find an example `g` where `force g` succeeds but both legal choices on a boundary edge lead to incorrect Tgraphs we will have a counter-example. If such a `g` exists then `superForce g` will raise an error. [The calculation of a boundary edge covering will call `atLeastOne` where both branches have led to failure for extending on an edge.]

This means that when `superForce` succeeds every resulting boundary edge has two legal extensions, neither of which will get stuck when forced.

I would like to thank Stephen Huggett who suggested the idea of using graphs to represent tilings and who is working with me on proof problems relating to the kite and dart tilings.

Reference [1] Martin Gardner (1977) MATHEMATICAL GAMES. Scientific American, 236(1), (pages 110 to 121). http://www.jstor.org/stable/24953856