In the article Tilings (by Ardila and Stanley) I read that a necessary and sufficient condition for a domino tiling to exist for some region with a checkerboard coloring, is that each group of $k$ white cells has at least $n \geq k$ black neighbors among them in the region.

The article then mentions that this is a specific case of the more general marriage theorem. I wanted to see if I can find a proof of the specific version, without introducing external concepts (such as representatives or neighborhoods); just using concepts that are already part of my tiling setup.**

I managed to specialize a proof, but it was very clunky until I introduced the following two concepts: a white patch is a set of white cells and all their neighbors. A white patch $P$ is bad if $|B(P)| < |W(P)|$ (where $W(P)$ is the set of white cells and $B(P)$ the set of black cells in $P$.) Similarly we can define a black patch and a bad black patch.

These concepts turn out to be useful not only in proving the theorem, but also in applications. For example, to prove that a geometric operation on a region does not affect its tileability we only need to show that the operation preserves bad patches. (I mean with "useful", easier to talk about; it's not like it's a new idea or to leads to new results AFAICS).

What I want to know is: Is there standard terminology for patches and bad patches, perhaps from graph theory or combinatorics? I mean, are these concepts already in use under different names?

** This is similar in spirit to what I was doing in Elementary proof of transformations of domino tilings.

  • $\begingroup$ I'm not aware of the patches terminology, but I have seen 'bad' used as an adjective for things that fail some wanted condition, although this applies broadly. "We call a set of vertices bad if..." and "We call a set of vertices good if it is not bad" are fairly common phrases. They're useful locally to make proofs and explanations easier, but should usually be defined explicitly when working in a new context. $\endgroup$ – Bob Krueger Jan 22 '18 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.