502 – König’s lemma (2)

We continue with the example of domino systems.

Remark 1 There is no algorithm that determines whether a given {D} can tile the plane or not.

Of course, for specific systems {D,} 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 {D} 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 {D}, 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 {D,} determines whether {D} can tile the plane or not, contradicting the remark above.

Begin by enumerating all pairs {(n,m)} with {n,m\ge1} as {(n_i,m_i).} For example, we can set {(n,m)=(n_i,m_i)} iff {i=2^{n-1}(2m-1).}

Since {D} is finite, we can produce a listing of all possible tilings by {D} of the {n_1\times m_1}-rectangle, then of all the tilings by {D} of the {n_2\times m_2}-rectangle, and so on.

Each of these listings is finite, since {D} is. At stage {i} we look at the tilings of {n_i\times m_i.} 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 {i} ends, and we go to stage {i+1.}

If {D} cannot tile the plane, then Theorem 2 from last lecture gives us that {D} cannot tile some finite square, so the algorithm will eventually stop, and output NO.

If {D} 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 {D} tiles the plane or not. This is a contradiction. \Box

A typical application of König’s lemma is in establishing compactness results.

Theorem 4 The interval {{}[0,1]} is compact.

Proof: Suppose a covering of {[0,1]} 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 {[0,1]} is the union of relatively open intervals with rational endpoints.

It then suffices to show that if {[0,1]} is covered by relatively open intervals with rational endpoints, then there is a finite subcovering. Say {(a_i,b_i),} {i\in{\mathbb N},} are the intervals that form the covering; to ease notation, replace intervals of the form {[0,a)} with {(-1,a),} intervals of the form {(a,1]} with {(a,2),} and {[0,1]} with {(-1,2).}

Define the dyadic intervals as those intervals of the form

\displaystyle I=\left[\frac{i}{2^n},\frac{i+1}{2^n}\right]

where {0\le i< 2^n.} In this case, we say that {I} is a dyadic interval of level {n.}

We will show that for some {n,} each dyadic interval of level {n} is covered by some {(a_i,b_i).} Otherwise, we can define a tree as follows: At level 1, we have {[0,1].} In general, at level {n+1} we have a collection of dyadic intervals of level {n,} none of which can be covered by some {(a_i,b_i).} Given such a dyadic interval {I,} its immediate successors are those dyadic intervals of level {n+1} that are contained in {I} (so there are at most two of them) and such that they cannot be covered either by some {(a_i,b_i).}

Our assumption grants that, for all {n,} there is at least one dyadic interval of level {n} 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

\displaystyle I_0\supset I_1\supset I_2\supset\dots

of dyadic intervals, none of which is covered by some {(a_i,b_i).} Moreover, {I_k} has length {2^{-k}} for each {k.}

It follows that {\bigcap_n I_n} consists of exactly one point, let’s call it {x.} Since the {(a_i,b_i)} cover {[0,1],} there is some {i} such that {x\in(a_i,b_i).} But then {I_k\subset(a_i,b_i)} for any sufficiently large {k,} and we have a contradiction. \Box

For our next example, define a graph {{\mathcal G}} as a pair {(V,G)} where {V} is a set (of vertices) and {G} is a collection of unordered pairs of elements of {V.} We refer to the elements of {G} as the edges of {{\mathcal G}.}

If {k} is a positive integer, a {k}-coloring of {{\mathcal G}} is a function {f:V\rightarrow k} such that whenever {v_0,v_1\in V} are distinct, and {\{v_0,v_1\}\in G,} then {f(v_0)\ne f(v_1).}

Exercise 2 Prove that a countable graph can be {k}-colored iff any finite subgraph can be {k}-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 {k}-sequence as a sequence with range contained in {k,} i.e., a sequence {u_0{}^\frown u_1{}^\frown\dots} where each {u_i\in\{0,\dots,k-1\}.}

Such a sequence {s} is {n}-free iff there is no finite nonempty sequence {x} such that the concatenation {x{}^\frown x{}^\frown\dots{}^\frown x} of {n} copies of {x} appears as a contiguous block in {s.}

  1. Show that there is no infinite {2}-free {2}-sequence.
  2. Use König’s lemma to show that there is an infinite {3}-free {2}-sequence iff there are arbitrarily long finite {3}-free {2}-sequences. Conclude the same about {2}-free {3}-sequences. 
  3. Let {\sigma:2^{<{\mathbb N}}\rightarrow2^{<{\mathbb N}}} be given by {\sigma(\emptyset)=\emptyset,} {\sigma(0)=0{}^\frown1,} {\sigma(1)=1{}^\frown0,} and {\sigma(u_0\dots u_m)=\sigma(u_0){}^\frown \dots{}^\frown\sigma(u_m).} Let {\sigma^n(s)} denote the {n}-th iterate of {s,} {\sigma^n(s)=\sigma(\dots(\sigma(s))\dots)} where there are {n} occurrences of {\sigma.}Show that {\sigma^n(0)} is {3}-free for each {n.} Conclude that there is an infinite {3}-free {2}-sequence. 
  4. Show that there is an infinite {2}-free {3}-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 {{\mathcal G}=({\mathbb N},G)} be a graph. Then there is an infinite {X\subseteq{\mathbb N}} such that either whenever {a,b\in X} and {a\ne b,} then {\{a,b\}\in G,} or else whenever {a,b\in X} and {a\ne b,} then {\{a,b\}\notin G.}

Put another way, any graph on {{\mathbb N}} either contains a copy of the infinite complete graph, or else it contains a copy of the infinite empty graph.

Proof: Let {x_0=0.} Either there are infinitely many {i>0} such that {\{x_0,i\}\in G} or else there are infinitely many {i>0} such that {\{x_0,i\}\notin G.} Whichever the case is, let {A_0} be the resulting infinite set and set {x_1={\rm min}(A_0).}

Now repeat, with {x_1} in the role of {x_0} and {A_0} in the role of {{\mathbb N}:} Either there are infinitely many {i>x_1,} {i\in A_0,} such that {\{x_1,i\}\in G,} or else there are infinitely many such {i} such that {\{x_1,i\}\notin G.} Let {A_1} be the resulting infinite set and set {x_1={\rm min}(A_1).} Continue this way.

This process generates a sequence {x_0<x_1<\dots} such that for all {i,} either:

  • {(0)_i:} For all {k>i,} {\{x_i,x_k\}\in G,} or else
  • {(1)_i:} For all {k>i,} {\{x_i,x_k\}\notin G.}

There are only two cases, so for some {j\in 2} there are infinitely many values of {i} such that {(j)_i} holds. Then

\displaystyle X=\{ x_i: (j)_i\mbox{ holds}\}

is as wanted. \Box

An immediate application of König’s lemma now gives us the following finitary result:

Corollary 6 For all {n} there is a number {N} such that whenever a graph has {N} or more vertices, it contains either a copy of the empty graph on {n} vertices, or a copy of the complete graph on {n} vertices.

Proof: Assume otherwise, and fix a counterexample {n.} Then, for each {N,} there is at least a graph on {N} vertices with no copy of either the empty graph on {n} vertices or the complete graph on {n} vertices. Put all these graphs in a tree by setting {{\mathcal G}} as an immediate successor of {{\mathcal G}'} if {{\mathcal G}'} can be obtained from {{\mathcal G}} 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 {{\mathcal G}_0,{\mathcal G}_1,{\mathcal G}_2,\dots} of graphs such that, for all {i}:

  1. {{\mathcal G}_{i+1}} is obtained from {{\mathcal G}_i} by adding one vertex and some (maybe none) edges between this vertex and old vertices from {{\mathcal G}_i,} and
  2. {{\mathcal G}_i} has no copy of the empty graph on {n} vertices, and no copy of the complete graph on {n} vertices.

Consider the graph {{\mathcal G}} 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 {n} vertices.

But this is impossible, since Ramsey’s theorem tells us that, in fact, {{\mathcal G}} has a copy of the infinite empty graph, or the infinite complete graph. \Box

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 {N} needs to be as a function of {n.}

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.

Advertisement

This entry was posted on Wednesday, August 26th, 2009 at 7:17 pm and is filed under 502: Logic and set theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

3 Responses to 502 – König’s lemma (2)

  1. Andrew Misseldine says:
    August 27, 2009 at 10:14 am

    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)?

    Reply
  2. andrescaicedo says:
    August 27, 2009 at 12:37 pm

    Hi Andrew,

    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.

    Reply
  3. 305 – Friedman’s theorem « Teaching blog says:
    February 4, 2012 at 5:11 pm

    […] Part II. […]

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: