In a domino tiling, a domino is exposed if it has a long edge that does not neighbor another domino. A domino that shares an edge with a long edge of another domino covers the edge (or the domino, if we understand which edge we mean) and prevents it from being exposed there.
In this image, exposed dominoes are in red. The blue domino's top edge is covered by the red domino above it.
A tiling with only horizontal dominoes of a $2\times 4$ rectangle has four exposed dominoes (all four are exposed), while a tiling of the same rectangle with only vertical dominoes has two exposed dominoes.
Does any finite domino tiling (with more than one domino) on the Euclidean plane have at least two exposed dominoes?
Trying to construct a counter example makes it seem "obvious", and after trying a few approaches I have hacked together a proof of this statement, but it is very clumsy and I would not be surprised if it misses cases and has errors. (Some earlier attempts failed because of all kinds of cases not considered).
So I am wondering if there is a neater proof of this statement.
Here is my attempt. (If this is an obvious fact with a simple proof you can skip this below and just point me in the right direction!)
Sketch
- I define a "top border" for a polyomino figure. In the figure above a top border is shown in green.
- I prove a figure must have a top border. (This is the really ugly part).
- I prove an exposed domino must exist by examining two cases:
- There are no vertical dominoes along the top border
- There is a vertical domino, and the left-most one is either exposed, or it is covered which means to the left of it is an exposed horizontal domino on the border.
An analogous definition and proof for the bottom border (yellow in the image) shows there is another exposed domino, and together this shows there must be at least two.
Other things I tried
- A graph-theory method. Here the difficulty was framing the problem - perhaps because I don't have much knowledge of this field - deciding what the vertexes and edges should be, and imposing all the constraints, and so on.
- Induction. Start with a domino. It has two edges. Adding a domino anywhere can only cover one edge and expose another. This turns out to be false (we have to do something more complicated to show that figures were we can kill long edges without exposing more edges can only arise if we added more edges than one at a time, or did not cover edges in each step. Even when getting around this difficulty, its difficult to show we cannot somehow loop around to bring two edges close enough so we can cover them both with a single domino.
- Contradiction. I assume a tiling with no exposed edges exist (in this version, I only try to prove at least one exposed domino must exist). I then attempt to prove we can take a top-most domino away, and transform the tiling if necessary using "flips" (changing the orientation of two dominoes in a $2\times 2$ square) to retain the no-exposed domino properties. Eventually, a minimal figure remains, for which (I thought), we can prove must have two edges. The proof fails because there are too many cases which I couldn't figure out how to keep the no-exposed property.
There were also a few other more bizarre attempts (like trying to show using a checkerboard color argument that if such a figure with no exposed dominoes exist it cannot be tilebale).
Detail
Starting from a vertex, we can describe a stretch of border going clockwise using letters $N$, $E$, $S$, $W$, which corresponds to the directions we have to move one unit to get to the next lattice point (which may correspond with a domino vertex, or the center of a long edge).
A top border is then the longest word (going clockwise), that contains any top-most domino edge, that starts with $N$, contains only $N$, $E$, $S$, and and ends with $E$. In the image, it's $NENEESE$.
To prove a figure has a top border, we construct it as follows:
- Pick a top-most domino and take the top-right vertex, and call it $A$. From here, traverse the border anti-clockwise, just before we get the first $W$ letter (note that the $W$ is clockwise, so from the anti-clockwise direction its actually east) and call this vertex $B$. Starting from $B$ going back clockwise towards $A$: the sequence must start with N, for:
- It cannot be $W$ (we stopped just before the first one),
- It cannot be $E$ ($E$ cannot proceed $W$)
- It cannot be $S$ (if it was, we would not be able to get back to $A$ without traveling $W$, which we cannot, going clockwise) (This is a dicey bit IMHO, it does not seem completely convincing.)
- Now let all of this (from $B$ to $A$) be the start of the top border. So far, it fulfills all the requirements of the definition (it starts with $N$, contains only $N$, $S$, $E$) except we may make it longer (only clockwise from $A$, since anticlockwise from $B$ we have a $W$).
- To make it longer, we go clock-wise all the way to the first $W$, then back track until the last $E$. Now we: start at $N$, end at $E$, and only have $N$, $S$ and $E$ in between - we have the top border.
To prove the top border has an expose domino, we consider two cases:
Case 1. the top border is made only from horizontally placed dominoes. In this case, find the top most one. It must be exposed, since the top edge cannot be covered by any domino (since it is at the top).
Case 2. the top border has a vertically-placed domino along the border. Find the one closest (along the border) to $B$. This vertical domino is either exposed, or only has horizontal dominoes placed between it and $B$ along the border. In the latter case, find the top-most of these horizontal dominoes. It cannot be covered at the top by a vertical domino (since if it is, this domino cannot be the one closest to $B$ along the border, since that domino is covered and two dominoes of different orientations cannot cover each other), and it cannot be covered by a horizontal domino (since its the top most), and therefor it is exposed.
Between these cases then, there must be an exposed domino in the top border.
We proceed similarly to define a bottom border (starting at $S$, ending with $W$ and containing only $S$, $N$ and $W$, $SWWWWNWNW$ in the image), and prove that there must be an exposed domino in the bottom border.
Note that the top and bottom borders don't overlap. Since a figure must have a top and bottom border, and each contains an exposed domino, and they don't overlap, the tiling must have at least two exposed dominoes.
