# Tag Archives: combinatorics

## Generating Functions

In this post we will discuss generating functions. Generating functions are a powerful tool which can be used to solve many problems both in combinatorics and also in analysis.

Let $R^\infty$ denote the set of all sequences of real numbers. For all $i\ge 1$ we let $x^i$ denote the sequence which has value $1$ for its $(i+1)$th term and all its other terms are zero. The symbol 1 stands for the sequence $(1,0,0,\cdots)$. Also for any real number $\alpha$ we define the product of $\alpha$ and a sequence $\alpha(a_0,a_1,\cdots)$ as $(\alpha a_0,\alpha a_1,\cdots)$. We let two sequences ${a_n}$ and ${b_n}$ be equal if $a_i=b_i$ for all $i$. We define the sum of ${a_n}$ and ${b_n}$ by the sequence ${a_n+b_n}$ and the product by the sequence ${c_n}$ where $c_i=\sum_{j=1}^ia_jb_{i-j}$. Clearly the sequence $(a_0,a_1,\cdots )$ is equal to the sequence $a_0+a_1x+a_2x^2\cdots$ which we will also denote simply by $\sum a_ix^i$. Note that $a_0$ here stands for the sequence obtained as a product of $a_0$ and 1, i.e. $a_0(1,0,0\cdots)$. Algebraically speaking $\mathbb {R}^\infty$, equipped with these operations, is an $\mathbb {R}$-algebra.

More importantly there is an analytic viewpoint of $\mathbb {R}^\infty$ also. Readers who are familiar with the theory of power series can consider the elements of $\mathbb {R}^\infty$ to be power series, i.e. each element is basically a function with its domain an open interval (or simply $\{0\}$). By standard theorems in analysis, if $\sum a_ix^i$ and $\sum b_ix^i$ both converge for $|x|0$ then for all such $x$, $\sum a_ix^i=\sum b_ix^i$ if and only if $a_i=b_i$ for all $i$. Hence the approach of considering $\sum a_ix^i$ as a purely formal object may be considered equivalent to considering it as a power series.

However, we will soon see as to why convergence issues do not play any role in our context as long as the power series converges for at least one non zero $x$ and there is more value in interpreting $\sum a_ix^i$ as simply an element of $\mathbb {R}^\infty$.

Definition:
Let $(a_n)$ be a real sequence such that the power series $\sum a_ix^i$ converges for at least one non zero $x$. Then the function $f$ which sends such an $x$ to the power series $\sum a_ix^i$ is called the generating function of the sequence. We frequently abuse notation and refer to the value of the generating function at some non-zero point $x$ as the generating function (which is akin to referring the function $f$ as $f(x)$).

Example:
Let $(a_n)$ be the constant sequence of one’s. It is well known that for any real number $x$, if $|x|<1$ the series $1+x+x^2+\cdots$ converges to $1/(1-x)$. So the generating function of $(a_n)$ is $f$ where $f(x)=1/(1-x)$ for all $x$ at which the series converges.

The reason for requiring convergence at a non zero point is as follows. As soon as we have convergence at a non zero $x$, by a theorem of analysis it follows that there is convergence in an open interval around $0$. Now, $f$ has a unique power series expansion in that interval and so we are guaranteed that there is a one-one correspondence between the purely discrete object $(1,1,\cdots)$ thought of as an element of $\mathbb{R}^\infty$ and the generating function $f$. This can be exploited in the reverse direction, for if we wish to recover our sequence from the function $f$, then since $f$ is defined by $f(x)=1/(1-x)=1+x+x^2+\cdots x^n$ there is absolutely no ambiguity, and we cannot get back any other sequence. In fact, we may say that our sequence has been encoded within the definition of $f$, as a closed form expression $1/(1-x)$ .

If convergence was only given at $0$, then such a one-one correspondence is not possible, since any closed form analytic function $f$, which is $a_0$ at $0$ would become the generating function to the sequence $(a_0,a_1,a_2,\cdots)$. So for any sequence $(a_0,a_1,\cdots)$ we will consider its generating function to be defined by $a_0+a_1x+a_2x^2\cdots$ as long as there is a non zero $x$ for which there is convergence, and once we have done that will not bother about any convergence issues at all.

The reader may be wondering what was the point of giving an algebraic approach initially, for a generating function really seems to have to do more with a power series. Furthermore in the notation of the first paragraph when we were considering a sequence as an element of $\mathbb{R}^\infty$ we gave found that in our algebra $(a_0,a_1,\cdots)$ is nothing but $a_0+a_1x+a_2x^2+\cdots$. This was not a power series but simply our notation for a sequence. It may appear confusing to have the same notation for two different objects, but it has been deliberately adopted for a very good reason. During our computations, we often manipulate our series so that we may no longer be sure whether convergence of a given series at a non-zero point is guaranteed. This poses a mathematical problem of the validity of our operations. However our ambiguous notation comes to our rescue at that instant, for what we really are doing at that point, without explicitly saying so, is not dealing with the series $a_0+a_1x+a_2x^2+\cdots$. Instead we are manipulating the sequence $a_0+a_1x+a_2x^2+\cdots=(a_0,a_1,a_2,\cdots)$ with which there are absolutely no concepts of convergence attached. Of course if we need closed form expressions or some other analytic properties have to be established we need convergence so that one can use the one-one correspondence between the sequence and the generating function and dive in the world of analysis. In this way, a constant interplay between the discrete world of sequences and the analytic world of sequences brings out the real power of generating functions.

Advertisements

1 Comment

Filed under Algebra, Combinatorics, Real Analysis

## The Inclusion Exclusion Principle

The Inclusion Exclusion Principle is one of most fundamental results in combinatorics. It deals with counting through a seive technique: i.e. we first overcount the quantity to be enumerated, then we try to balance out the overcounting by subtracting the extra. We may or may not subtract more then what is needed and so we count again the extra bits. Continuing in this way we “converge” at the correct count.

An easy example is $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$ where $A,B,C$ are three finite sets.

Here we start off by summing the number of elements in $A,B,C$ seperately. The overcount is compensated by subtracting the number of elements in $|A\cap B|$,$|A\cap C|$, $|B\cap C|$. We actually compensate for a bit more then needed and so to arrive at the correct count we must add $|A\cap B\cap C|$.

Our goal here is to prove the inclusion-exclusion principle and then to look at a few corollaries. We first establish two lemmas.

Lemma 1: If $X$ is any set containing $n$ elements and $k$ is any field, then the set of all functions $f:X\to k$ is an $n$-dimensional vector space $V$ over $k$ with the naturally induced operations.

Proof: Let $X=\{x_1,\cdots,x_n\}$. It is easy to see that $V$ together with the operations $f+g$, defined by $(f+g)(x_i)=f(x_i)+g(x_i)$ and $(\alpha f)(x_i)=\alpha (f(x_i))$ for all $x_i\in X$ is a vector space.

We now exhibit a basis for $V$ consisting of $n$ elements. For all $x_i\in X$ let $f_{x_i}$ be the function defined as $f_{x_i}(y)=\begin{cases} \hfill 1 \hfill & \text{ if }y=x_i \\ \hfill 0 \hfill & \text{ otherwise} \\ \end{cases}$. Now, we claim that $B=\{f_{x_i}:x_i\in X\}$ is a basis. Clearly it is spanning as for any $f\in V$ we have $f=\sum_{x_i\in X}f(x_i)f_{x_i}$. It is linearly independent as $\sum_{x_i\in X} \alpha_i f_{x_i}=0$ means that for any $j$, with $1\le j\le n$, we have $\sum_{x_i\in X} \alpha_i f_{x_i}(x_j)=0$, i.e. $\alpha_j=0$. This completes the proof.$\Box$

Lemma 2: If $m\ge 0$ then $\sum_{i \mathop = 0}^m \left({-1}\right)^i \binom m i = \delta_{0m}$.

Proof: If $m>0$ put $x=1, y=-1$ in the binomial theorem $(x+y)^m=\sum_{i=0}^mx^{m-i}y^i$. If $m=0$, then the sum on the left reduces to only one term: $(-1)^0\binom 0 0$. This is clearly $1$.$\Box$

We now prove the Inclusion Exclusion principle. This theorem in its purest form, is simply a formula for an inverse of a linear operator. The theorem is as follows:

Theorem 3: Let $S$ be a set with $n$ elements. Let $V$ be the $2^n$ dimensional vector space of all functions $f:\mathcal{P}(S)\to k$, where $k$ is some field and $\mathcal{P}(S)$ is the power set of $S$. Let $\phi:V\to V$ be the linear operator defined by

$\displaystyle\phi f(T)=\sum_{Y\supseteq T}f(Y)\text{ for all } T\subseteq S.$

Then $\phi^{-1}$ exists and is given by:

$\displaystyle\phi^{-1} f(T)=\sum_{Y\supseteq T}(-1)^{|Y-T|}f(Y)\text{ for all } T\subseteq S.$

Proof: To show $\phi^{-1}$ as given above is indeed the inverse it suffices to show that $\phi^{-1}\phi(f)=f$ for all $f\in V$.

Let $f\in V$. Then,

$\displaystyle\phi^{-1}\phi f(T)=\sum_{Y\supseteq T}(-1)^{|Y-T|}\phi f(Y)=\sum_{Y\supseteq T}(-1)^{|Y-T|}\sum_{Z\supseteq Y}f(Z)=\sum_{Z\supseteq T}\Big(\sum_{Z\supseteq Y\supseteq T}(-1)^{|Y-T|}\Big)f(Z)$

Now fix $Z,T$ and let $m=|Z-T|$. Consider $\displaystyle\sum_{Z\supseteq Y\supseteq T}(-1)^{|Y-T|}$. Any $Y$ is obtained by choosing some elements out of $Z-T$ which has $m$ elements, and taking the union of such elements with $T$. So for every $i$, with $0\le i\le m$, there are exactly $\binom m i$ ways of choosing a $Y$, which has $i+|T|$ elements. Any such $Y$ also has $i$ elements in $|Y-T|$. So $\displaystyle\sum_{Z\supseteq Y\supseteq T}(-1)^{|Y-T|}=\sum_{i=0}^m(-1)^i\binom m i=\delta_{0m}$. This when substituted in the expression for $\phi^{-1}\phi f(T)$ shows that $\phi^{-1}\phi f(T)=f(T)$, which proves the theorem.$\Box$

We now discuss some corollaries of the Inclusion Exclusion principle. Let $S$ be a set of properties that elements of a given set $A$ may or may not have. For any $T\subseteq S$, let $A'_T\subseteq A$ be those elements which have exactly the properties in $T$ and no others. We define a function $f_=:S\to \mathbb{R}$ such that $f_=(T)=|A'_T|$. Similarly, for any $T\subseteq S$, let $A''_T\subseteq A$ be those elements which have at least the properties in $T$. We define a function $f_\ge:S\to \mathbb{R}$ such that $f_=(T)=|A''_T|$. It is clear that $\displaystyle f_\ge(T)=\sum_{Y\supseteq T}f_=(T)$ for any $T\subseteq S$, and so by the Inclusion Exclusion principle we conclude that

Corollary 4: For any $T\subseteq S$, we have $\displaystyle f_=(T)=\sum_{Y\supseteq T}(-1)^{|Y-T|}f_\ge (Y)$.

In particular we have $\displaystyle f_=(\emptyset)=\sum_{Y\subseteq S}(-1)^{|Y|}f_\ge (Y)$, which gives us a formula for the number of elements having none of the properties.$\Box$

In the above corollary we think of $f_\ge(T)$ as the first approximation to $f_=(T)$. So we “include” that much “quantity” in our initial count. From this we subtract all terms of the type $f_=(Y)$ where $Y$ has just one extra element then $T$. Thus we “exclude” that much “quantity” from our count. This gives a better approximation. Next we add all terms of the type $f_=(Y)$ where $Y$ has two extra elements then $T$, and so on. This is the reason behind the terminology inclusion-exclusion.

We now discuss another corollary. Let $A$ be a finite set and let $A_1,\cdots A_n$ be some of its subsets. We define a set of properties $S=\{P_1,\cdots,P_n\}$ which elements of $A$ may or may not enjoy as follows: For any $i$, with $1\le i\le n$, $x\in A$ satisfies the property $P_i$ if and only if $x\in A_i$. Also for any $I\subseteq [n]$, let $\emptyset\ne A_I=\cap_{i\in I}A_i$ be the set of elements which have at least the properties $P_i$ for $i\in I$. Define $A_\emptyset$ to be $A$. By Corollary 4, $\displaystyle f_=(\emptyset)=\sum_{I'\subseteq S}(-1)^{|I'|}f_\ge (I')=\sum_{I\subseteq [n]}(-1)^{|I|}|A_I|$ where in the second equality we correspond each subset of properties with a subset of $[n]$. We summarize this as

Corollary 5: Let $A$ be a finite set and let $A_1,\cdots A_n$ be some of its subsets. For any $\emptyset\ne I\subseteq [n]$, let $A_I=\cap_{i\in I}A_i$ and let $A_\emptyset=A$. The number of elements in $A-\cup_{i=1}^n A_i$ is given by $\displaystyle\sum_{I\subseteq [n]}(-1)^{|I|}|A_I|=|A|+\sum_{\emptyset\ne I\subseteq [n]}(-1)^{|I|}|A_I|$.$\Box$

A further special case is obtained by considering any finite sets $A_1,A_2,\cdots,A_n$ and letting $A=\cup_{i=1}^nA_i$. Then the above corollary translates to $\sum_{I\subseteq [n]}(-1)^{|I|}|A_I|=0$. Considering the case of $I=\emptyset$ seperately, we see that $|A|+\displaystyle\sum_{\emptyset\ne I\subseteq [n]}(-1)^{|I|}|\cap_{i\in I}A_i|=0$. This easily yields the following corollary.

Corollary 6: Let $A_1,A_2\cdots,A_n$ be any finite sets. For any $\emptyset\ne I\subseteq [n]$, let $A_I=\cap_{i\in I}A_i$ and let $A_\emptyset=A$. Then $\displaystyle|A_1\cup A_2\cup\cdots\cup A_n|=\displaystyle\sum_{\emptyset\ne I\subseteq [n]}(-1)^{|I|-1}|\cap_{i\in I}A_i|$.$\Box$

Now by grouping terms involving the same size of $I$ we can restate both Corollary 5 and 6 as follows.

Corollary 7: Let $A$ be a finite set and let $A_1,\cdots A_n$ be some of its subsets. The number of elements in $A-\cup_{i=1}^n A_i$ is given by
$\displaystyle |A|+\sum_{k=1}^n(-1)^{k}\sum_{1\le i_1 < i_2 < \cdots .$\Box$

Corollary 8: If $A_1,A_2\cdots,A_n$ are any finite sets then

$\displaystyle|A_1\cup A_2\cup\cdots\cup A_n|=\sum_{k=1}^n(-1)^{k-1}\sum_{1\le i_1< i_2<\cdots.$\Box$

Corollaries 5 to 8 are often referred to as the principle of inclusion-exclusion themselves as in combinatorial settings they are the ones most often used. A further simplified version can also be derived from them when the intersection of any $k$ distinct sets $A_i$ always has the same cardinality $N_k$. In that case we only need to multiply $N_k$ with the number of such ways to select the $k$ sets to get the value of the inner sums in Corollaries 7 and 8.

Corollary 9: Let $A$ be a finite set and let $A_1,\cdots A_n$ be some of its subsets. Suppose that for any $k$ with $1\le k\le n$ there exists a natural number $N_k$ so that for any $\{i_1,\cdots, i_k\}\subseteq [n]$ we have $A_{i_1}\cap\cdots\cap A_{i_k}=N_k$. Then the number of elements in $A-\cup_{i=1}^n A_i$ is given by $|A|+\sum_{k=1}^n(-1)^k\binom{n}{k}N_k$ and $|A_1\cup A_2\cup\cdots\cup A_n|=\sum_{k=1}^n(-1)^{k-1}\binom{n}{k}N_k$.$\Box$

Leave a comment

Filed under Combinatorics, Set 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$

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

## Arrows, Ramsey numbers and the Party Problem

Here come the arrows! The notation $\alpha\rightarrow (\beta)^2_r$ means that every $r$-colored complete graph on $\alpha$ vertices contains a monochromatic complete subgraph with $\beta$ vertices. Using the notation $\omega$ for the cardinality of the natural numbers the abridged Ramsey theorems state that $\omega\rightarrow (\omega)^2_r$ and that $\forall n\exists m,m\rightarrow (n)^2_r$.

Now let us take a particular case: $n=3,r=2$. Our objective here is to prove that $6\rightarrow (3)^2_2$. In other words, if the edges of $K_6$ are $2$-colored then there exists a monochromatic $K_3$. Fix a vertex $v$ in $K_6$. From the $5$ edges emanating from $v$, at least three must share a color: call it $c$. Now if all the edges in triangle made by those three vertices are not colored $c$, we are done for we have found a monochromatic $K_3$ in the other color. If even one edge, say $xy$ among the triangle made by those three vertices is of color $c$ then we have a monochromatic $K_3$ colored $c$ with vertices $x,y$ and $v$.

The fact that $6\rightarrow (3)^2_2$ is also referred to as the solution of the party problem: Prove that in any gathering of six people there are three mutual friends, or three mutual strangers. By representing the people as vertices and their relationships via the colors on the edges connecting them we easily see that a monochromatic triangle is guaranteed and therefore the result holds. It is also obvious that the gathering may contain more then six people, a monochromatic triangle is still guaranteed within (in fact, it will only become more likely with more people). In other words: $m\rightarrow (3)^2_2\forall m\ge 6$.

Is six the least such number? Indeed it is as the following graph demonstrates:

We note that there is no monochromatic triangle in the above $2$-colored $K_5$.

For a given $n$ the least such number $m,m\rightarrow (n)^2_r$ is called the diagonal Ramsey number $R(n,n)$. While such numbers are guaranteed to exist by Ramsey’s theorem, actually finding them is hard indeed. It is trivial to see that $R(1,1)=1$ and $R(2,2)=2$. Our proof above illustrates that $R(3,3)=6$. It has also been proven that $R(4,4)=18$. However all efforts to find out the exact value of any other diagonal Ramsey number have failed. It is one of those problems, which are easily stated but extremely difficult to attack.

Regarding $R(5,5)$, Joel Spencer comments in his book, Ten lectures on the Probabilistic Method:

Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of $R(5,5)$ or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for $R(6,6)$. In that case, he believes, we should attempt to destroy the aliens.

In closing it may be remarked that the Ramsey number $R(m,n)$ is defined to be the least positive integer such that any $2$-coloring of $K_{R(m,n)}$ in two colors, say red and blue, contains either a red $K_m$ or a blue $K_n$. This definition also has the natural generalization for more then two colors. Although the existence of all Ramsey numbers is guaranteed by Ramsey’s theorem, only few have been discovered so far.

1 Comment

Filed under Combinatorics, Miscellaneous, 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