Category Archives: Graph theory

Graph Automorphisms

This post is concerning automorphisms of graphs, which quantify the symmetry existing within the graph structure. Given two graphs G and H, a bijection f:V(G)\to V(H) which maintains adjacency, i.e. xy\in E(G)\Leftrightarrow f(x)f(y)\in E(H), is called an isomorphism and the graphs G and H are called isomorphic. Clearly isomorphic graphs are essentially the same, with the superficial difference between them on account of different notation used in defining the vertex set. A isomorphism from the graph G to itself is called an automorphism. It is easy to see that the set of all automorphisms on a graph G together with the operation of composition of functions forms a group. This group is called the automorphism group of the graph, and is denoted by A(G).

In the remainder of this post we investigate some well known graphs and find out their automorphism groups.

The first graph we take up is the complete graph K_n. Any permutation of its n vertices is in fact an automorphism for adjacency is never lost. Its automorphism group is therefore S_n.

The next graph is the complete bipartite graph K_{m,n}. First consider the case m\not= n. The m vertices in the first partite set can be permuted in m! ways and similarly n! ways for the second partite set. Corresponding to each of these m!n! limited permutations we get automorphisms because adjacency is never disturbed. On the other hand, no automorphism can result from swapping a vertex from the first partite set and the second partite set because unless such a swap is done in its entirety (i.e. all the vertices from the first partite set swap places with the vertices in the second partite set), adjacency will be lost. A swap can be done in entirety only if m=n which is not the case we are considering. Hence no further automorphisms can result. Moreover by the multiplication rule it is simple to observe that the automorphism group would be isomorphic to S_m\times S_n.

In the case of m=n, we first pair off the vertices in the two partite sets against each other. This is also an automorphism, say f. Now for each of the m!m! ways of permuting vertices within partite sets, an additional automorphism arises. It is obtained in this fashion: After permuting the vertices within the partite sets by the particular way we swap each vertex with its pair in the other partite set. Clearly this yields 2m!m! automorphisms and furthermore no more are possible. Since every element of A(K_{m,m}) can be written as a unique product of an automorphism collection of the type covered in counting the first m!^2 ways (which is not hard to see is a normal subgroup, being of index 2) and of the subgroup \{Id,f\} so we see that the automorphism group is S_m\times S_m\rtimes \mathbb{Z}_2.

The next graph we take up is the cycle graph C_n. Firstly note that any automorphism can be obtained in this way: A given vertex v may be mapped to any of the n vertices available (including itself). As soon as that is done, an adjacent vertex to v has only two choices left: it can either be in the counter clockwise direction to v or in the clockwise direction to v. Once that choice is also made, no other choices are required. Hence we get 2n automorphisms this way and there can be no others. Also, it is clear that two kinds of automorphisms suffice to generate this group: rotation, and swapping the notion of clockwise and counter clockwise (assuming we draw the cycle graph as equally spaced points on the unit circle; there is no loss of generality in doing that). But both these automorphisms also generate the dihedral group D_n which also has 2n elements. It follows that A(C_n)=D_n.

The final graph we take up is the well known Petersen graph. Instead of directly considering what possible functions are there in its automorphism group (although such an approach is possible) we approach the problem through the concept of line graphs.

Definition: A line graph L(G) of a graph G is the graph whose vertices are in one to one correspondence with the edges of G, two vertices of L(G) being adjacent if and only if the corresponding edges of G are adjacent.

Lemma 1: L(K_5) is the complement of the Petersen graph.
Proof: It is clear that if the vertices of K_5 are labelled 1,2,\ldots,5 then its 10 edges are the {5 \choose 2} 2-subsets of \{1,\cdots,5\}. The line graph L(K_5) thus has 10 vertices, labeled by these 10 2-subsets \{i,j\}. Two vertices \{i,j\}, \{k,\ell\} are adjacent in L(K_5) iff the two 2-subsets have a nontrivial overlap. The complement of L(K_5) is the graph with the same 10 vertices, and with two vertices being adjacent iff the corresponding two 2-subsets are disjoint. But this is the very definition of the Petersen graph.\Box

Lemma 2: A(G) is equal to A(\bar{G}).
Proof: If \sigma\in A(G) then for any two vertices x,y we have xy\in E(G)\Leftrightarrow \sigma(x)\sigma(y)\in E(G), i.e. xy\not\in E(G)\Leftrightarrow \sigma(x)\sigma(y)\not\in E(G), i.e. xy\in E(\bar{G})\Leftrightarrow \sigma(x)\sigma(y)\in E(\bar{G}) so that \sigma\in A(\bar{G}). The reverse implication follows by replacing G by \bar{G}. \Box

Theorem 3: The automorphism group of the Petersen graph is S_5.
Proof: In view of Lemma 1 and 2 it suffices to find out A(L(K_5)) for the automorphism group of the Petersen graph is going to be the same. We let K_5 have the vertex set \{1,\cdots,5\} in the sequel.

Take any automorphism f of K_5. If we have two edges ab,cd\in K_5 with f(a)f(b)=f(c)f(d), then either of two cases arise. Either f(a)=f(c) or not. If f(a)=f(c) then obviously f(b)=f(d) and so by injectivity of f we have ab=cd. If f(a)\not=f(c) then it must be that f(a)=f(d). This means that f(b)=f(c) and again by injectivity we have ab=cd. What this means is that the function induced by f on E(K_5) in the natural way is injective. It is also surjective as for any xy\in E(K_5) clearly f\{f^{-1}xf^{-1}y\}=xy. Finally, this function is an automorphism since \{xy,xz\}\in E(L(K_5)) clearly implies and is implied by \{f(x)f(y),f(x)f(z)\}\in E(L(K_5)) as there is a common vertex. As our definition of the induced function is obtained in a definite way we have shown that every automorphism of K_5 induces a unique automorphism of L(K_5). Moreover, it is easy to see that if f_1,f_2 are two automorphisms then the automorphism induced by f_1\circ f_2 is the same as the automorphism induced by f_1 composed by f_2.

We now show that given an automorphism of L(K_5) we can obtain an automorphism of K_5 which induces it in the natural way. Let \pi\in A(L(K_5)). It is easy to see that the 4-cliques of L(K_5) originate from the stars K_{1,4} of K_5. So L(K_5) has exactly 5 4-cliques, say C_1,\cdots ,C_5 where C_i contains 4 vertices corresponding to the 4 edges in K_5 that are incident to a vertex i in K_5. Since \pi is an automorphism it sends 4-cliques to 4-cliques. Also, \pi must send two different 4-cliques C_i,C_j with i\ne j to different 4-cliques, because if it sends them to the same 4-clique then a collection of at least 5 vertices is mapped to a collection of 4 vertices, a contradiction to the injectivity of \pi. So \pi induces a permutation of the C_i‘s.

Now suppose \pi and \pi' are two different automorphisms in A(L(K_5)). Then they differ on at least vertex in L(K_5), say on the vertex ij\in E(K_5). Now given any vertex xy in L(K_5) consider the intersection of the 4-cliques C_x and C_y. If pq is some vertex in C_x\cap C_y then pq as an edge in K_5 is part of stars with centers x and y, i.e. pq=xy. Hence the intersection contains only the vertex xy. Every vertex of L(K_5) arises in this way. So if \pi(ij)\ne \pi'(ij), then either \pi (C_i)\ne \pi'(C_i) or \pi(C_j)\ne \pi'(C_j) for otherwise \pi (C_i\cap C_j)=\pi'(C_i\cap C_j).

Hence every automorphism of L(K_5) induces a unique permutation of the C_i‘s. Moreover distinct automorphisms induce distinct permutations so that the automorphisms and the permutations can be put in one-one correspondence. Consider an automorphism f of the vertices of K_5 where f(i)=j if C_i\to C_j in the permutation corresponding to \pi. Now a vertex \{x,y\}\in E(K_5) of L(K_5). This is also the intersection of the 4-cliques C_x and C_y and so \pi(\{x,y\})=\pi(C_x\cap C_y)=\pi(C_x)\cap\pi (C_y)=C_{f(x)}\cap C_{f(y)}=f(x)f(y). This shows that f induces \pi as an automorphism.

Hence we have shown that A(K_5)\equiv A(L(K_5)). So the Petersen graph has the automorphism group S_5. \Box

Advertisements

Leave a comment

Filed under Combinatorics, Graph theory, Group Theory

Bipartite graphs

The topic of this post is bipartite graphs. These are graphs whose vertex set can be partitioned into two parts, called partite sets, such that all edges xy of the graph are such that x and y are in different partite sets. The most common examples of bipartite graphs are the trees and even cycles. Any union of bipartite graphs obviously yields another bipartite graph. The complete bipartite graph K_{m,n} consists of two partite sets X and Y containing m and n elements respectively with all possible edges between X and Y filled out.

To conclude here is a list of characterizations.

Suppose G is a graph with at least two vertices. The following are equivalent:

1. G is bipartite.

2. Every cycle of G is even.

3. \chi(G)=2.

Proof:
1 \Leftrightarrow 2: Suppose G is bipartite and there is a cycle v_1v_2\cdots v_kv_1 which has an odd number of edges. Now v_i for odd i is in the same partite set as v_1. But since the cycle is odd v_1 and v_k are in the same partite set which is a contradiction.

Conversely suppose G has no odd cycles and x\in V(G). Let X=\{y\in V(G):d(x,y) is even \} and Y=\{y\in V(G):d(x,y) is odd \}. Then X and Y partition V(G). Suppose pq\in E(G) and p,q\in X. Neither p nor q is x for otherwise d(x,q) (resp d(x,p)) is odd. So it makes sense to talk of a path from x to p (resp q). Let x=v_0v_1\cdots v_{2k-1}v_{2k}=p and x=w_0w_1\cdots w_{2m-1}w_{2m}=q be the shortest such paths. (Note that they are necessarily even). Let the last common vertex in the two paths be v_i=w_i. Now the cycle v_iv_{i+1}\cdots v_{2k}w_{2m}w_{2m-1}\cdots w_{i+1}w_i=v_i is an odd cycle. This contradiction proves there are no edges within vertices of X. Similarly there are no edges within vertices of Y. The result follows.

1 \Leftrightarrow 3: This is more of a restatement of the definition of a bipartite graph then a characterization, since the two partite sets may be considered as differently colored subsets of V(G).\Box

In addition to the above general characterizations the following are also true:

a) G is bipartite iff the spectrum of G is symmetric with respect to the origin.

b) Suppose G is connected and \lambda is its maximum eigenvalue. Then G is bipartite iff -\lambda is an eigenvalue of G.

c) Suppose G is planar. Then G is bipartite iff b(R), the bound degree of a region R, is even for every region R.

I will defer a proof of these statements.

Leave a comment

Filed under Combinatorics, Graph theory

On unabridged versions of Ramsey’s theorem

In continuation of our discussions on Ramsey theory in this post we plan to prove the unabridged versions of Ramsey’s theorem. While the abridged versions dealt with graphs, unabridged versions deals with hypergraphs. A hypergraph, is a set of vertices V together with a set of subsets of V of a fixed order n. If n=2 then we get back the ordinary definition of a graph.

An example of a hypergraph of order 3 is given below:

The vertex set V=\{a,b,c,d,e\} and the hyperedges are given by: \{a,b,c\}, \{b,d,e\} and \{a,b,d\}.

The infinite unabridged version of Ramsey’s theorem may now be described as follows: Given a complete infinite hypergraph of order n with vertex set \mathbb{N}, and a r-coloring of its hyperedges we are guaranteed a infinite complete monochromatic subgraph.

Let us try to express this more succinctly. We will extend the previously defined arrows notation as follows: The notation \alpha\rightarrow (\beta)^n_r will mean that every r-colored complete hypergraph of order n on \alpha vertices contains a monochromatic complete subgraph with \beta vertices. Since hypergraphs do not seem to be as picturesque as graphs, so maybe the idea will be better expressed in terms of sets: \alpha\rightarrow (\beta)^n_r equivalently means that for any assignment of r-colors to the n-subsets of \alpha, there is a particular color (say red) and a subset X of \alpha of size \beta such that all n-subsets of X are red. (Note that \alpha,\beta etc can be any cardinal numbers.)

With the notation that \omega stands for the cardinality of \mathbb{N} the infinite version of Ramsey’s theorem now is:

Theorem: \forall n,r\in\mathbb{N}, \omega\rightarrow(\omega)^n_r.

The proof is essentially on the same lines as in the abridged case, with the addition that we induct on n. (n may intuitively be thought of as the “hyper-ness” of our hypergraph.)

Proof: By induction on n. If n=1 we just get the infinite pigeonhole principle: Any finite partitioning of \mathbb{N} contains an infinite part. Indeed, both the infinite and finite Ramsey theorems may be thought of as gigantic generalizations of the pigeonhole principle.

Now suppose that for a fixed n,r we have \omega\rightarrow(\omega)^n_r. Now consider any r-coloring f of the n+1-subsets of \omega. Just like in the proof of the abridged case we build a sequence (w_k). In the abridged case we applied the infinite pigeonhole principle repeatedly at this point. Here we will use the induction hypothesis repeatedly. Let w_1=1. Consider the r-coloring f_{w_1} of all n-subsets of \omega-\{1\} given by f_{w_1}(X)=f(\{1\}\cup X). By the induction hypothesis there will be a countable subset of \omega whose all n-subsets will be monochromatic. Call that subset V_1. Let the least element of V_1 be designated as w_2.

The construction of (w_k) follows by induction: If the set V_k and its least element w_{k+1} have been found, consider the r-coloring f_{w_{k+1}} of the n-subsets of V_k given by f_{w_{k+1}}(X)=f(\{w_{k+1}\}\cup X). By the induction hypothesis it contains a countable set all of whose n-subsets are monochromatic. Call that subset V_{k+1}. Its least element is designated as w_{k+2}.

The sequence (w_k) has the property that given any w_i the union of \{w_i\} with any n-order subset containing elements from w_{i+1},w_{i+2},w_{i+3}\cdots has the same color (with respect to the the original coloring f). Let us call w_i as c_j-based if this color is c_j. The fact that all the members of the sequence (w_k) are based in any of r-ways induces a partitioning of the sequence (w_k). By the infinite pigeonhole principle we are guaranteed an infinite part. Now, by ordering the terms appropriately in this infinite part we have a subsequence (w_{k_j}) of (w_k) in which all vertices are the same color base, say c_1. It is now easy to observe that all the n+1-subsets of this infinite part are colored c_1, which proves the theorem.\Box

We now turn to the finite version. In our arrows notation, the natural generalization from the abridged analogue reads:

Theorem: \forall l,n,r\in\mathbb{N}, \exists m\in\mathbb{N} such that m\rightarrow (l)_r^n.

Proof: The proof is identical to the abridged case with cosmetic changes. By way of contradiction assume that there is an l such that for all m\in\mathbb{N} we have m\nrightarrow (l)_r^n. We will use the notation \hat{K_i} for a hypergraph on i vertices where all possible n-subsets of the vertices are the hyperedges. Also let G be a hypergraph with vertices V=\{v_i:i\in\mathbb{N}\} and let the hyperedges of G be enumerated by E=\{E_i:E_i\subset\mathbb{N}, |E_i|=n\}. We construct a (rooted) tree T as follows:

1. First introduce a root vertex rt.

2. Each vertex is allowed to have at most r children which correspond to the r-colors, subject to it satisfying the criteria below. A child is always labeled by one among the r-colors. (Call the colors c_1,c_2\cdots c_r for convenience).

3. A child c_i is permitted if and only if its introduction creates a path of some finite length k starting from the root, so that if the hyperedges E_1,E_2\cdots E_k are colored by the colors used in the path in the same order, then the corresponding subgraph in G does not contain a monochromatic \hat{K_l}. For example if the introduction of a child c_i creates the k length path rt,c_a,c_b\cdots ,c_i and the hyperedges E_1,E_2,\cdots E_k when colored c_a,c_b\cdots c_i don’t contain a monochromatic \hat{K_l} the child c_i is permitted to be added to T.

Note that for all m, there always exists a coloring of \hat{K_m} such that no monochromatic \hat{K_l} exists within. So the situation that a child cannot be added to any vertex at a given level k cannot arise. For we can always take a coloring of \hat{K_{k+n}} containing no monochromatic \hat{K_l}. Since any k hyperedges in it would yield a sequence of colors already existing in T, we know which vertex to add the child to. We give the child the color corresponding to any other edge. Hence we can forever keep adding children and so T is infinite. It is also obvious that each level k of T has at most r^k vertices and so each level is finite.

Now by Konig’s lemma there will be an infinite path in T. This infinite path provides a r-coloring of G that contains no monochromatic \hat{K_i} and hence no monochromatic infinite hypergraph which contradicts the infinite Ramsey theorem proved above. This contradiction proves the theorem.\Box

The astute reader may have noted that we have used weak versions of the axiom of choice occasionally in the proof. Ramsey himself was aware of this and remarked so in his original paper. In fact, it can be proved that Ramsey’s theorem cannot ever be proved without using some form of the axiom of choice. Moreover it can be shown that a weak form of the axiom of choice is equivalent to Ramsey’s theorem. Hence Ramsey’s theorem may be interpreted as a choice axiom.

1 Comment

Filed under Combinatorics, Graph theory, Ramsey theory

On abridged versions of Ramsey’s theorem

This post will aim to prove two abridged versions of Ramsey’s theorem, the result which gave its name to the area of mathematics now known as Ramsey theory. Ramsey theory may be understood as ramifications of a philosophical principal. The principle may be summarized as: “Complete disorder is an impossibility. Any structure will necessarily contain an orderly substructure.” Ramsey’s theorem is an example of this principle. Van der Waerden’s theorem is another example.

First a bit of history regarding this theorem. Frank Ramsey, a 25 year old British mathematician, proved this result in 1928 as a part of his investigations in mathematical logic. Unfortunately he passed away in 1930 (even before his theorem was formally published) and did not prove anything else related to this. In 1933, Skolem published another proof of the theorem, and then in 1934, Erdos and Szekeres found yet another. It was the Erdos and Szekeres paper which gave Ramsey’s theorem a wide audience. Further work by Erdos in this area led mathematicians to consider other Ramsey type theorems.

Here we consider abridged versions of Ramsey’s theorem which can be easily understood in the context of graphs. We will imitate Ramsey’s original approach (though not his proof) to first prove an infinite version (which deals with infinite graphs) and then proceed towards the finite analogue.

So what is the infinite version. Briefly it says that if we have an infinite complete graph on countable vertices and if we use r colors c_1,c_2\cdots c_r to arbitrarily color the edges then we are guaranteed an infinite monochromatic subgraph. Here our usage of coloring an edge is just a fanciful way to describe partitioning the edge set into finitely many parts. More formally, by a r-coloring of the edges of a graph G we mean any function with domain E(G) and range \{1,2\cdots r\} which induces such a partitioning. The colors are the labels that we may use for this partitioning.

Theorem: Let G be the complete infinite graph with vertices V=\{v_i:i\in\mathbb{N}\}. Given any r-coloring of the edges, G will contain an infinite complete monochromatic subgraph.

Ramsey’s original formulation was more general. He considered the set of vertices to be any infinite set (and not just countable). That is not much gained because a coloring of an uncountable vertex graph induces a coloring of a countable vertex subgraph. Within this countable subgraph we can find a monochromatic infinite complete graph, which is also a subgraph of the original. However he also generalized in another sense: Instead of coloring edges he considered colorings of hyperedges of a fixed order (an edge is a special case: it is a hyperedge of order 2). This too can be overcome by induction on the “hyper-ness” of the graph. We choose to postpone such discussions.

Proof: Suppose the edges of G have been colored using the colors c_1,c_2,\cdots c_r. We will build an infinite subsequence of the vertices in V by applying the infinite pigeonhole principle. Let w_1=v_1. Now w_1 is connected with every other vertex in G and the edges making this connection are colored in any of r-ways. We partition the set of all these vertices in this fashion: If v is connected to w_1 via an edge colored c_i we consider it to be a member of the set P_i. Clearly, \{P_i:i=1,2\cdots r\} is a partitioning of V-\{w_1\}. Now, since \cup P_i is infinite so one of the P_i must also be infinite. (Here we are using the infinite pigeonhole principle.) Note that there may be more then one infinite P_i. At any rate choose the “smallest” vertex among the infinite parts (or the vertex with the least i in \{v_i:i\in P_j, P_j is infinite \}. Rename that particular P_i as V_1 and that vertex as w_2.

At this point the construction of the sequence becomes obvious. If for some n we have already found a w_n and and a V_n then we can partition the vertices in V_n connected to w_n into r-parts depending on how they are connected with w_n. Choosing the smallest vertex among the infinite parts yields w_{n+1} and the part it belongs to yields V_{n+1}. Since V_{n+1} is infinite so we have no fear of running out of vertices.

Now note an important property of the sequence (w_n). Given any w_i its connections with w_{i+1},w_{i+2},w_{i+3}\cdots are all of the same color by definition. Let us call w_i as c_j-based if the edges w_iw_{i+1},w_iw_{i+2},w_iw_{i+3}\cdots are all colored c_j. The fact that all the members of the sequence (w_n) are based in any of r-ways induces a partitioning of the sequence (w_n). As before by the pigeonhole principle we are guaranteed an infinite part. Now, by ordering the terms appropriately in this infinite part we have a subsequence (w_{n_k}) of (w_n) in which all vertices are the same color base, say c_1. It is now easy to observe that the subgraph induced by these vertices has all edges colored c_1, which proves the theorem.\Box

We now turn our attention to the finite analogue. The infinite version guarantees an infinite monochromatic complete graph within an arbitrarily colored infinite countable graph (with countable vertices). The finite version guarantees a finite monochromatic complete graph of desired size within an arbitrarily colored finite countable graph (with suitable number of vertices). More formally the theorem states:

Theorem: Let r,l_1,l_2,\cdots l_r be natural numbers. Then there exists an m\in \mathbb{N} such that any r-coloring of K_m contains a monochromatic K_{l_i} for some i entirely colored in color i.

We will prove the theorem with l_1=l_2=\cdots =l_r=n. This is because no loss of generality occurs by assuming this. To see this suppose r=2,l_1=5 and l_2=7. Now if we have proved the theorem for r=2,l_1=l_2=7 we have also guaranteed the existence of an m such that any 2-coloring of K_m contains a K_7 colored in either of the two colors. Clearly the same m works for l_1=5,l_1=7 as a 1-colored K_7 would contain a 1-colored K_5.

Proof: Our modified claim is that for all r,n\in\mathbb{N} there is an m\in\mathbb{N} such that any r-coloring of K_m contains a monochromatic K_n. By way of contradiction assume that there is an n\in\mathbb{N} such that for every m\in \mathbb{N} there is a r-coloring of K_m containing no monochromatic K_n. Now let G be a complete graph with vertices V=\{v_i:i\in\mathbb{N}\} and let the edges of G be enumerated by E=\{e_i:i\in\mathbb{N}\}. We construct a (rooted) tree T as follows:

1. First introduce a root vertex rt.

2. Each vertex is allowed to have at most r children (a child of a vertex x is defined to be an adjacent vertex y so that d(rt,x)+1=d(rt,y)) which correspond to the r-colors, subject to it satisfying the criteria below. A child is always labeled by one among the r-colors. (Call the colors c_1,c_2\cdots c_r for convenience).

3. A child c_i is permitted if and only if its introduction creates a path of some finite length k starting from the root, so that if the edges e_1,e_2\cdots e_k are colored by the colors used in the path in the same order, then the corresponding subgraph in G does not contain a monochromatic K_n. For example if the introduction of a child c_i creates the k length path rt,c_a,c_b\cdots ,c_i and the edges e_1,e_2,\cdots e_k when colored c_a,c_b\cdots c_i don’t contain a monochromatic K_n the child c_i is permitted to be added to T.

Note that for all m, there always exists a coloring of K_m such that no monochromatic K_n exists within. So the situation that a child cannot be added to any vertex at a given level k cannot arise. For we can always take a coloring of K_k containing no monochromatic K_n. Since any k edges in it would yield a sequence of colors already existing in T, we know which vertex to add the child to. We give the child the color corresponding to any other edge. Hence we can forever keep adding children and so T is infinite. It is also obvious that each level k of T has at most r^k vertices and so each level is finite.

Now by Konig’s lemma there will be an infinite path in T. This infinite path provides a r-coloring of G that contains no monochromatic complete graph and hence no monochromatic infinite complete graph which contradicts the infinite Ramsey theorem proved above. This contradiction proves the theorem.\Box

3 Comments

Filed under Combinatorics, Graph theory, Ramsey theory

A ball game and Konig’s lemma

In this post we will examine an application of Konig’s lemma to investigate a game proposed by Raymond Smullyan.

Imagine there is an unlimited supply of balls with us, with positive integers painted on each. It is very much possible that a particular positive integer is repeated many times on various balls. We do not know anything else about the distribution of numbers on the balls. Further imagine that there is a box with a ball initially within it.

To play the game we may do either of two things:

(1) We may remove a ball from the box and replace it with any finite number of balls, arbitrarily chosen, but constrained to have numbers painted on them which are less then the number of the ball removed. For example, if we have a number 1000 ball we may remove it and replace it by 6000 balls: 3000 balls on which 657 is painted, and 3000 balls on which 999 is painted.

(2) We may remove a ball from the box and not do any replacement.

After playing the game once we can continue playing provided there are balls left in the box.

The question is: Is it possible to play the ball game indefinitely? Can we ensure that the box will never be empty?

Smullyan himself answered this problem in the negative by using Konig’s lemma.

Theorem: The Smullyan game terminates after a finite number of steps.

Proof: For any play of the Smullyan game define a (rooted) tree as follows:
1. The vertices are the painted balls used during the game.
2. The root is the painted ball intially within the box.
3. The edges are given by the following criteria: There is an edge between the vertices x and y iff during some move of the game, the ball y is among the balls which replaces the ball x (or vice-versa).

By the definition of the game this is a rooted tree where each level is finite. Can there be an infinite path in the tree? No there can’t. This is because, by definition an infinite path would correspond to a infinite strictly decreasing sequence of positive integers which is absurd. By the contrapositive form of Konig’s lemma we can therefore conclude that the tree is finite. In other words only finitely many balls were used and so the game terminated after finitely many steps.

An alternate proof without using Konig’s lemma is available here.

Leave a comment

Filed under Game Theory, Graph theory, Miscellaneous

Konig’s lemma

This post is about trees. Not real-life ones but mathematical trees, or more formally about acyclic connected graphs. Just as actual big skinny trees are tall, graph theoretic big skinny trees are also tall. The goal here is to prove this formally.

But first some definitions. A tree is called labeled if every vertex has been assigned a symbol, called its label. A fixed vertex in a tree may be labelled as r and referred to as its root. The level i in a tree is the collection of all vertices at a fixed distance i from the root. Admittedly these definitions are informal and may be formalized in terms of directed graphs.

An example of a labelled tree is given below:

Here r is the root and the vertex sets \{a,b\} and \{1,2,3\} are at level 1 and 2 respectively. Clearly this labeling is arbitrary and any other labeling is also possible.

We now prove our result. It is due to Konig, a Hungarian professor of mathematics, who had Erdos amongst his students. It is called a lemma because it was initially used by Konig to investigate another theorem (see this) . As often happens it has turned out to be a powerful tool to use on many other problems as well.

Lemma: If T is an infinite tree and each level of T is finite then T contains an infinite path.

Proof: Suppose T is a labeled tree with root r. Let L_0=\{r\}, L_1,L_2,\cdots be the levels of T. We construct our path by starting with r. Next we partition all vertices in levels higher then L_0 (i.e. all vertices in levels L_i where i>0) into as many finite parts as is the cardinality of L_1. In other words if L_1=\{v_1,\cdots v_n\} then we partition the vertices (there are infinitely many of them) in n parts: P_1,P_2\cdots P_n. This partitioning is done as follows: Any vertex w will be connected to r via some v_i owing to connectedness. We put w in P_i.

Now since we have partitioned infinitely many vertices in finitely many parts, one of the parts will contain infinitely many vertices.(This is also called the infinite pigeonhole principle). Let that part be P_j. Choose w_1=v_j as the next vertex in our under-construction path. Next we delete the vertex r and consider the component containing w_1. It is also an infinite tree with each level finite and having w_1 as its root. By a similar piece of reasoning, we get a vertex w_2 which is adjacent to w_1 and has infinitely many vertices corresponding to it. We continue building our path by choosing w_2 as a part of it. By induction we can continue and get an infinite path rw_1w_2\cdots. This proves the theorem.\Box

It should be noted that at each of the infinitely many stages of selecting the w_i we choose it out of a finite set: the finite set of vertices at that level each of which correspond to infinite parts in the current partitioning. There is no canonical way to make this choice. To ensure that this can be done we need to use a weak form of the axiom of choice: Let X\ne\emptyset and \mathcal{F}(X) be the collection of all finite subsets of it. Then there is a function f:\mathcal{F}(X)-\emptyset\to X such that f(x)\in x\forall x\in \mathcal{F}(X)-\emptyset. A curious fact is that Konig’s lemma in turn applies this weak form of the axiom of choice and so both of them are equivalent. While their equivalence can be established using the ZF axioms, obviously neither can be proved within ZF.

3 Comments

Filed under Combinatorics, Graph theory