\input fremtex
\smallprint
\def\lectureend#1{}
\def\Caption{}
\atUEssex
\filename{ma251b1.tex}
\versiondate{15.1.96}
\copyrightdate{1996}
\oldfootnote{}{These notes are made available to students on the understanding that they have not been properly checked for errors, nor do they necessarily cover the topics to be examined in the course, which are determined by the material covered in lectures.}
\Centerline{\bf MA251 Combinatorics}
\medskip
\noindent{\bf 1. Binomial coefficients}
\medskip
{\bf 1A The definitions} For integers $r$, $n$ with $0\le r\le n$ we have four possible definitions of the binomial coefficient $^nC_r$:
\inset{(i) $^nC_r=\Bover{n!}{r!(n-r)!}$;}
\inset{(ii) $^nC_r$ is the number of subsets of size $r$ of a given set of size $n$;}
\inset{(iii) $^nC_r$ is the number appearing in Pascal's triangle
\vskip 5pt
\centerline{1}
\centerline{1\quad 1}
\centerline{1\quad 2\quad 1}
\centerline{1\quad 3\quad 3\quad 1}
\centerline{1\quad 4\quad 6\quad 4\quad 1}
\centerline{$\ldots$}
\vskip 5pt
\noindent (as the $(r+1)$-st number in the $(n+1)$-st line);}
\inset{(iv) $^nC_r$ is the coefficient of $a^rb^{n-r}$ in the binomial expansion of $(a+b)^n$.}
\noindent The importance of these numbers is signalled by this variety of different ways in which they can be described. My own preference is for (ii); I believe that this is really the root reason why binomial coefficients turn up so often.
\medskip
{\bf 1B Proof of equality} We must check that the definitions (i)-(iv) in 1A do indeed all give the same numbers; possible arguments are as follows.
\medskip
{\bf (a) Equivalence of (i) and (ii)} Suppose we have a set $X$ with $n$ elements, listed as $\{x_1,\ldots,x_n\}$. Let us count the number of ways of putting these in order. This is just $n!$, because we have $n$ choices for which element we take first, then $n-1$ choices for the second, $n-2$ choices for the third, $\ldots$, finishing with just one choice for the last, making $n(n-1)(n-2)\ldots 1=n!$ possibilities altogether.
On the other hand, we could do the ordering by the following method:
\inset{($\alpha$) pick out a set $A$ of $r$ elements of $X$, to be the first
$r$ elements in the final ordering;}
\inset{($\beta$) put these in order at the front;}
\inset{($\gamma$) put the elements of $X\setminus A$ in order at the back.}
\noindent If we followed this scheme, we should have $\#([X]^r)$ choices at step ($\alpha$), where
\Centerline{$[X]^r=\{A:A\subseteq X,\,\#(A)=r\}$}
\noindent is the set of $r$-element subsets of $X$; $r!$ choices at step ($\beta$), because $\#(A)=r$; and $(n-r)!$ choices at step ($\gamma$), because $\#(X\setminus A)=n-r$. So this makes
$r!(n-r)!\#([X]^r)$ ways of doing it altogether, and this must be equal to $n!$, got by counting the same set in a different way. Thus
\Centerline{$n!=r!(n-r)!\#([X]^r)$,
\quad$\#([X]^r)=\Bover{n!}{r!(n-r)!}$,}
\noindent which is what we had to prove, since 1A(i) defines $^nC_r$ to be $\bover{n!}{r!(n-r)!}$, while 1B(ii) defines it to be $\#([X]^r)$.
\medskip
{\bf Equivalence of (i) and (iii)} Induce on $n$. For this argument, write $^nC_r$ for $\bover{n!}{r!(n-r)!}$ and $P_{n,r}$ for the corresponding number in Pascal's triangle. Then
\Centerline{$P_{0,0}=1=\Bover{0!}{0!0!}=\ ^0C_0$,}
\noindent and if $n=0$ this is the only thing to check, so the induction starts. For the inductive step to $n\ge 1$,
\Centerline{$P_{n,0}=1=\Bover{n!}{0!n!}=\ ^0C_n$,
\quad$P_{0,n}=1=\Bover{n!}{n!0!}=\ ^nC_n$,}
\noindent and if $0\#(V)$}
\noindent by the inductive hypothesis. Moreover, there is a path from
$a$ to $b$ in $G'$, and therefore a simple path (2E); suppose it is
$(a\,\ldots\,b)$; then we can add $a$ at the end to make a cycle
$(a\,\ldots\,b\,a)$ in $G$, as required. Thus in this case also the
induction continues.
\medskip
{\bf 2H Corollary} Let $G=(V,E)$ be a non-empty finite graph. Then the
following are equiveridical:
(i) $G$ is a tree;
(ii) $G$ is connected and $\#(V)\ge\#(E)+1$;
(iii) $G$ has no cycles and $\#(V)\le\#(E)+1$;
\noindent and in this case $\#(V)=\#(E)+1$.
\medskip
\noindent{\bf proof (a)} If $G$ is a tree, then (by definition) it is
connected and has no cycles, so (because it is not empty) it has exactly
one component, and
\Centerline{$\#(V)=\#(E)+1$}
\noindent by 2G. Thus (i) implies (ii) and (iii).
\medskip
{\bf (b)} If (ii) is true, then again $\#(V)\le\#(E)+1$, by 2G, and
since we must in this case have equality, 2G tells us that there are no
cycles, that is, that $G$ is a tree.
\medskip
{\bf (c)} Finally, if (iii) is true, then by 2G we have
$\#(V)=\#(E)+\#(\Cal C)$, where $\Cal C$ is the set of components of
$G$, so $\#(\Cal C)\le 1$; thus $G$ is connected and must be a tree.
\medskip
{\bf 2I Adding degrees: Lemma} In any finite graph $G=(V,E)$,
\Centerline{$\sum_{v\in V}d(v) = 2\#(E)$.}
\medskip
\noindent{\bf proof} Consider the set
\Centerline{$R=\{(v,e):v\in V,\,e\in E,\,v$ is an endpoint of $e\}$.}
\noindent Then
$$\eqalign{\#(R)&=\sum_{v\in V}\#(\{e:(v,e)\in R\})=\sum_{v\in V}d(v)\cr
&=\sum_{e\in E}\#(\{v:(v,e)\in R\})=2\#(E).\cr}$$
\medskip
{\bf 2J Proposition} Suppose that $G=(V,E)$ is a non-empty finite graph
in which every
vertex has degree at least 2. Then $G$ has a cycle of length at least
3.
\medskip
\noindent{\bf proof} By 2I,
\Centerline{$\#(E)=\Bover12\sum_{v\in V}d(v)\ge\#(V)$.}
\noindent Also, because $V\ne\emptyset$, the set $\Cal C$ of components
of $G$ is also not empty, so $\#(E)+\#(\Cal C)>\#(V)$; by 2G, $G$ has a
cycle.
\lectureend{95/6, 96/6}
{\bf $^*$2K Counting trees} There is a beautiful result (Theorem 2M
below) giving the total number of trees which can be formed on a given
set of vertices; unfortunately it must be regarded as outside the
syllabus of this course, but I write it out anyway. First a
definition: if $G=(V,E)$ is a graph, a {\bf leaf} in $G$ is a vertex of
degree precisely 1.
\medskip
{\bf $^*$2L Lemma} If $L\subseteq V$, write $\Cal T_{VL}$ for the set of
trees with vertex set $V$ in which $L$ is the set of leaves. If $W$ is
any set and $n\in\Bbb N$, write $F_{nW}$ for the set of surjective
functions from $\{1,\ldots,n\}$ onto $W$. Then whenever $n\ge 3$, $V$
is a set of size $n$, and $L\subseteq V$,
\Centerline{$\#(F_{n-2,V\setminus L})=\#(\Cal T_{VL})$.}
\medskip
\noindent{\bf proof (a)} Note first that any tree on a set of two or
more vertices must have a leaf. \Prf\ Because it is connected, every
vertex has degree at least 1. Because there is no cycle, there must be
a vertex of degree less than 2, by 2J. \Qed
So if $\#(V)=n\ge 3$ and $L=\emptyset$, $\Cal T_{VL}=\emptyset$; but
also $F_{n-2,V\setminus L}=\emptyset$ because $\#(V\setminus L)>n-2$.
So in this case
\Centerline{$\#(F_{n-2,V\setminus L})=0=\#(\Cal T_{VL})$.}
\medskip
{\bf (b)} Now induce on $n$.
\medskip
\quad{\bf (i)} If $n=3$, then the only trees on $V$ are simple chains
with two leaves, and there is just one of them for each doubleton set of
leaves; while $F_{1,V\setminus L}=\emptyset$ unless $V\setminus L$ is a
singleton, and in this case has just one element. So we have
$$\eqalign{\#(F_{1,V\setminus L})=\#(\Cal T_{VL})
&=0\text{ if }\#(L)\ne 2,\cr
&=1\text{ if }\#(L)=2.\cr}$$
\medskip
\quad{\bf (ii)} For the inductive step to $n>3$, take $L\subseteq V$
where $\#(V)=n$. If $L=\emptyset$ then $\#(F_{n-2,V})=\#(\Cal
T_{V\emptyset})=0$, by (a). If $L\ne\emptyset$, take any $v\in L$.
\qquad\grheada\ If $T\in\Cal T_{VL}$, then $v$ is linked by an edge in
$T$ to exactly one $u\in V$, and $u\notin L$, because otherwise
$\{u,v\}$ would be a component of $T$. So
\Centerline{$\#(\Cal T_{VL})=\sum_{u\in V\setminus L}\#(\{T:T\in\Cal
T_{VL},\,v$ is linked to $u$ in $T\})$.}
\noindent On the other hand, if $T\in\Cal T_{VL}$ and $v$ is linked to
$u$ by an edge in $T$, then $T-v$, the graph obtained from $T$ by
deleting the vertex $v$ and the edge $(u\,v)$, is again a tree. The
set of leaves of $T-v$ must be either $L'=L\setminus\{v\}$ or
$L'\cup\{u\}$; that is, $T-v$ belongs either to $\Cal T_{V',L'}$ or to
$\Cal T_{V',L'\cup\{u\}}$, where $V'=V\setminus\{v\}$. Accordingly
\Centerline{$\#(\Cal T_{VL})=\sum_{u\in V\setminus L}\#(\Cal
T_{V'L'})+\#(\Cal T_{V',L'\cup\{u\}})$.}
\qquad\grheadb\ Now look at $F_{n-2,V\setminus L}$. Every
$f\in F_{n-2,V\setminus L}$ can be identified with a pair $(g,u)$, where
$u=f(n-2)$ and $g$ is the restriction of $f$ to $\{1,\ldots,n-3\}$.
Moreover, in this case, the set of values of $g$ must be either
$V\setminus L=V'\setminus L'$ or $V'\setminus(L'\cup\{u\})$. So the
total number of such pairs is
\Centerline{$\sum_{u\in V\setminus L}\#(F_{n-3,V'\setminus L'})
+\#(F_{n-3,V'\setminus(L'\cup\{u\}})$,}
\noindent and this is $\#(F_{n-2,V\setminus L})$.
\qquad\grheadc\ Putting these together,
$$\eqalignno{\#(\Cal T_{VL})
&=\sum_{u\in V\setminus L}\#(\Cal T_{V'L'})
+\#(\Cal T_{V',L'\cup\{u\}})\cr
&=\sum_{u\in V\setminus L}\#(F_{n-3,V'\setminus L'})
+\#(F_{n-3,V'\setminus(L'\cup\{u\}})\cr
\noalign{\noindent (by the inductive hypothesis, since $\#(V')=n-10,\,v=v_i\})$,}
\noindent because the first counts the number of steps in the path which
start at $v$, and the second counts the number of steps finishing at
$v$; and every edge with $v$ as an endpoint must appear exactly once as
one or other of these. But this sum is necessarily even if $v$ is not
equal to $v_0$ or $v_n$, odd if $v=v_0\ne v_n$ or $v=v_n\ne v_0$, and
even again if $v=v_0=v_n$. So if the path is closed, every vertex has
even degree, while if it is not closed then $v_0$ and $v_n$ have odd
degree and all other vertices have even degree. Since this marks out
$v_0$ and $v_n$ as the only vertices of odd degree, any other Eulerian
path must start at one and end at the other.
If the path is closed, then (because $G$ is connected) it passes through
any given vertex $a$, so we can start and finish the circuit at $a$.
\lectureend{95/7}
\medskip
{\bf 3D Theorem} Suppose that $G=(V,E)$ is a non-empty finite connected
graph in which every vertex has even degree. Then it has an Eulerian
circuit.
\medskip
\noindent{\bf proof} Induce on $m=\#(E)$. If $m=0$ then $V$ must be a
singleton $\{v\}$ (because $G$ is non-empty and connected), so that
$(v)$ is a trivial Eulerian circuit.
For the inductive step to $m>0$, we know that $G$ has more than one
vertex; because it is connected, $d_G(v)\ge 1$ for every $v\in V$;
because every vertex has even degree, $d_G(v)\ge 2$ for every $v$; so
$G$ has a non-trivial cycle $(v_0\,v_1\,\ldots\,v_n)$, where $v_n=v_0$
(2J). Let $G'=(V,E')$ be the graph obtained by deleting all the
edges used in this cycle. Then $d_{G'}(v)$ is either $d_G(v)-2$ (if
$v=v_i$ for some $i$) or $d_G(v)$, and in either case is even, for every
$v\in V$. Of course $G'$ need not be connected; let $V_1,\ldots,V_r$
be its components. Then for every $k\le r$ there is a $j(k)$ such that
$v_{j(k)}\in V_k$. \Prf\ Starting from any $a\in V_k$, there is a path
$Q$ from $a$ to $v_0$ in $G$, because $G$ is connected. This meets the
set $\{v_1,\ldots,v_n\}$ in some first point $v_i$ (possibly $a$
itself); now the segment of $Q$ from $a$ to $v_i$ is a path in $G'$, so
$v_i$ belongs to the same component of $G'$ as $a$ does, and we can take
$j(k)=i$. \Qed\ Note that if $k\#(S\cup T)$}
\noindent and $S$, $T$ must overlap; say $j\in S\cap T$. Note that $1\notin T$ and $n-1\notin S$, so $1r(v)$. Also
$(v_0\,\ldots\,v_{r-1}\,v\,w)$ is a path from $v_0$ to $w$, so $r(w)\le
r(v)+1$; but this means that $r(w)=r(v)+1$ and $f(w)\ne f(v)$.
($\beta$) Otherwise, $i2(2^{m_1+m_2-1}-1)$,}
\noindent so there is some $j$ such that $\#(X_j)>2^{m_1+m_2-1}-1$, that
is, $\#(X_j)\ge 2^{m_1+m_2-1}$. Set $m'_j=m_j-1$, $m'_i=m_i$ if $i\ne
j$, so that $\#(X_j)\ge 2^{m'_1+m'_2}$. Look at $f_1=f\restr
[X_j]^2:[X_j]^2\to\{1,2\}$. By the inductive hypothesis, there is a
set $A\subseteq X_j$ such that, for some $i$, $\#(A)=m'_i$ and
$f_1(I)=i$ for every $I\in[A]^2$. If $i=j$, set $B=A\cup\{x\}$; if
$i\ne j$, set $B=A$. Then $\#(B)=m_i$ and $f(I)=i$ for every
$i\in[B]^2$. \Prf\ (i) If $i=j$, then $\#(B)=m'_i+1=m_i$. If
$I\in[B]^2$, either $I\subseteq A$ and $f(I)=f_1(I)=i$, or $I=\{x,y\}$
for some $y\in V_j$; but in this case $f(I)=j=i$ by the definition of
$V_j$. (ii) If $i\ne j$ then $\#(B)=m'_i=m_i$ and $f(I)=f_1(I)=i$ for
every $I\in[B]^2$. \Qed
Thus the induction proceeds.
\medskip
{\bf 6G Corollary} Let $G=(V,E)$ be a finite graph of order at least
$2^{m+n}$. Then {\it either} $K_m$ is a subgraph of $G$ {\it or} $K_n$
is a subgraph of $\overline{G}$.
\medskip
\noindent{\bf proof} For $I\in[V]^2$, set $f(I)=1$ if there is an edge
in $E$ linking the two vertices in $I$, $2$ otherwise. By 6F, there is
a set $A\subseteq V$ such that either $\#(A)=m$ and $f(I)=1$ for every
$I\in[A]^2$, or $\#(A)=n$ and $f(I)=2$ for everyb $I\in[A]^2$. In the
first case, $G\restr A$ is a complete graph on $m$ vertices; in the
second case, $\overline{G}\restr A$ is a complete graph on $n$ vertices.
\medskip
{\bf 6H Ramsey numbers (a)} The numbers $2^{m_1+m_2}$ in 6F, $2^{m+n}$
in 6G are certainly much larger than necessary. For instance, if $G$
is a graph of order 6, at least one of $G$, $\overline{G}$ has $K_3$ as
a subgraph. \Prf\ (i) Suppose $G$ has a vertex $x$ of degree 3 or
more. In this case, take a set $A$ of 3 vertices linked to $x$ by an
edge. If no two vertices in $A$ are linked by an edge in $G$, then
$\overline{G}\restr A$ is a complete graph on three vertices. If two
vertices $y$, $z\in A$ are linked by an edge in $G$, then
$G\restr\{x,y,z\}$ is a complete graph on three vertices. (ii) Suppose
$G$ has a vertex $x$ of degree $2$ or less. Then $x$ has degree at
least 3 in $\overline{G}$, so we can use the same argument again. \Qed
(Another way of looking at it: if you have six people gathered
together, either there are three people present who all know each other,
or there are three people present none of whom know each other.)
(That assumes that the relation `knowing each other' is symmetric.
If you take your duties as a host seriously you will know very well that
this isn't really true.)
\medskip
{\bf (b)} In fact 6 is the magic number here: if you consider the
simple cycle on 5 vertices
\picture{251-bb16}{30pt} %a 5-cycle
\noindent then its complement is also a simple cycle and neither has
$K_3$ as a subgraph.
\medskip
{\bf (c)} In general, we can talk about the {\bf Ramsey numbers}
$R(m,n)$: $R(m,n)$ is the smallest number such that whenever $G$ is a
graph of order $R(m,n)$, then either $K_m$ is a subgraph of $G$ or $K_n$
is a subgraph of $\overline{G}$. Of course $R(m,n)=R(n,m)$. We have
$R(0,n)=0$, $R(1,n)=1$, $R(2,n)=n$ (if $K_2$ is not a subgraph of $G$,
then $G$ has no edges, so $K_n$ will be a subgraph of $\overline{G}$
provided there are $n$ vertices). After this it gets difficult. I
believe that very few of the $R(m,n)$ are known exactly; it may well be
that the calculation is `intractable' in the same sense that the
travelling salesman problem is intractable.
\medskip
{\bf (d)} We can ask some of the same questions about infinite graphs;
this leads into very deep water. But the first result is relatively
easy.
\medskip
{\bf 6I Ramsey's theorem: infinite form} Let $f:[\Bbb N]^2\to\{1,2\}$
be any function. Then there is an infinite set $A\subseteq\Bbb N$ such
that $f$ is constant on $[A]^2$.
\medskip
\noindent{\bf proof} Define $n_1n_k,\,f(\{n_k,n\})=1\}$,
\quad$C''_k=\{n:n\in C_k,\,n>n_k,\,f(\{n_k,n\})=2\}$.}
\noindent If $C'_k$ is infinite, set $i_k=1$, $C_{k+1}=C'_k$.
Otherwise, because $C'_k\cup C''_k=C_k\setminus\{n_k\}$ is infinite,
$C''_k$ must be infinite; set $i_k=2$, $C_{k+1}=C''_k$. Continue.
Note that at each stage of the induction,
$C_{k+1}\subseteq C_k\setminus\{n_k\}$, so that $n_k