We continue with the example of domino systems.
Remark 1 There is no algorithm that determines whether a given can tile the plane or not.
Of course, for specific systems we usually can tell by ad hoc methods which one is the case. What the remark above indicates is that there is no uniform way of doing this.
Corollary 3 There is a system that can tile the plane, but not periodically.
Proof: This is an example of a non-constructive proof. We will argue by contradiction, so that at the end we will know that there is such a system , but we will have no information about what it looks like.
Assume that every system that can tile the plane, can tile it periodically. Our goal is to build an algorithm that, given a system determines whether can tile the plane or not, contradicting the remark above.
Begin by enumerating all pairs with as For example, we can set iff
Since is finite, we can produce a listing of all possible tilings by of the -rectangle, then of all the tilings by of the -rectangle, and so on.
Each of these listings is finite, since is. At stage we look at the tilings of If it happens that there are no tilings, then the algorithm stops and outputs NO. If it happens that there is one such tiling that generates a periodic tiling of the plane, then the algorithm stops and outputs YES. Otherwise, stage ends, and we go to stage
If cannot tile the plane, then Theorem 2 from last lecture gives us that cannot tile some finite square, so the algorithm will eventually stop, and output NO.
If can tile the plane, our assumption is that it can do so periodically, and so the algorithm will eventually stop, and output YES.
This shows that the algorithm always stops, and correctly identifies whether tiles the plane or not. This is a contradiction.
A typical application of König’s lemma is in establishing compactness results.
Theorem 4 The interval is compact.
Proof: Suppose a covering of by relatively open sets is given. We need to find a finite subcovering.
There are only countably many rational numbers, so there are only countably many intervals with rational endpoints. Any relatively open subset of is the union of relatively open intervals with rational endpoints.
It then suffices to show that if is covered by relatively open intervals with rational endpoints, then there is a finite subcovering. Say are the intervals that form the covering; to ease notation, replace intervals of the form with intervals of the form with and with
Define the dyadic intervals as those intervals of the form
where In this case, we say that is a dyadic interval of level
We will show that for some each dyadic interval of level is covered by some Otherwise, we can define a tree as follows: At level 1, we have In general, at level we have a collection of dyadic intervals of level none of which can be covered by some Given such a dyadic interval its immediate successors are those dyadic intervals of level that are contained in (so there are at most two of them) and such that they cannot be covered either by some
Our assumption grants that, for all there is at least one dyadic interval of level in the tree, so all levels of the tree are nonempty, and the tree is infinite. It is clearly finite branching so, by König’s lemma, it has an infinite branch. This corresponds to a decreasing sequence
of dyadic intervals, none of which is covered by some Moreover, has length for each
It follows that consists of exactly one point, let’s call it Since the cover there is some such that But then for any sufficiently large and we have a contradiction.
For our next example, define a graph as a pair where is a set (of vertices) and is a collection of unordered pairs of elements of We refer to the elements of as the edges of
If is a positive integer, a -coloring of is a function such that whenever are distinct, and then
Exercise 2 Prove that a countable graph can be -colored iff any finite subgraph can be -colored.
This is true even for uncountable graphs, but something stronger than König’s lemma is needed then. The celebrated four-color theorem of Appel and Haken states that any planar graph is 4-colorable. This is usually presented with the additional restriction that the graph is finite. Both versions are equivalent, by the remarks just mentioned.
The following exercise is from Kaye’s book mentioned above.
Exercise 3 Define a -sequence as a sequence with range contained in i.e., a sequence where each
Such a sequence is -free iff there is no finite nonempty sequence such that the concatenation of copies of appears as a contiguous block in
- Show that there is no infinite -free -sequence.
- Use König’s lemma to show that there is an infinite -free -sequence iff there are arbitrarily long finite -free -sequences. Conclude the same about -free -sequences.
- Let be given by and Let denote the -th iterate of where there are occurrences of Show that is -free for each Conclude that there is an infinite -free -sequence.
- Show that there is an infinite -free -sequence.
In the examples above we have used König’s lemma to deduce infinitary results from finite versions. The opposite is also possible. A typical and important example comes from Ramsey theory.
Theorem 5 (Ramsey) Let be a graph. Then there is an infinite such that either whenever and then or else whenever and then
Put another way, any graph on either contains a copy of the infinite complete graph, or else it contains a copy of the infinite empty graph.
Proof: Let Either there are infinitely many such that or else there are infinitely many such that Whichever the case is, let be the resulting infinite set and set
Now repeat, with in the role of and in the role of Either there are infinitely many such that or else there are infinitely many such such that Let be the resulting infinite set and set Continue this way.
This process generates a sequence such that for all either:
- For all or else
- For all
There are only two cases, so for some there are infinitely many values of such that holds. Then
is as wanted.
An immediate application of König’s lemma now gives us the following finitary result:
Corollary 6 For all there is a number such that whenever a graph has or more vertices, it contains either a copy of the empty graph on vertices, or a copy of the complete graph on vertices.
Proof: Assume otherwise, and fix a counterexample Then, for each there is at least a graph on vertices with no copy of either the empty graph on vertices or the complete graph on vertices. Put all these graphs in a tree by setting as an immediate successor of if can be obtained from by removing one vertex (and all the edges attached to it).
This is an infinite finite branching tree, so König’s lemma grants us the existence of an infinite branch, i.e., a sequence of graphs such that, for all :
- is obtained from by adding one vertex and some (maybe none) edges between this vertex and old vertices from and
- has no copy of the empty graph on vertices, and no copy of the complete graph on vertices.
Consider the graph obtained by taking the union of the graphs in this sequence. This is an infinite graph without a copy of either the empty or the complete graph on vertices.
But this is impossible, since Ramsey’s theorem tells us that, in fact, has a copy of the infinite empty graph, or the infinite complete graph.
Corollary 6 can also be obtained by standard counting arguments. The disadvantage of invoking König’s lemma (combinatorialists say “invoking compactness”) is that the argument above gives us no clue as of how large needs to be as a function of
In a few special cases, a deep result from logic (Herbrand’s theorem) can be used to extract such functions from uses of König’s lemma, but in general these arguments are nonconstructive.
Typeset using LaTeX2WP. Here is a printable version of this post.
I’m a little uncertain about when the homework is due. You said on Monday that you wanted Homework Exercise 1 due on Next Monday. For the exercises from Wednesday, are these due also on next Monday or are they due on next Wednesday (a week after they were assigned)?
For now, homework is due a week after it is assigned, so the exercises from Wednesday are due this coming Wednesday, while Exercise 1 is due Monday.
[…] Part II. […]