\documentstyle[12pt,twoside,amstex]{article}

\addtolength{\topmargin}{-1in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\raggedbottom

\input{macros-course}

\newtheorem{falsethm}[theorem]{False Theorem}
\newtheorem{fact}{Fact}
\newtheorem{axiom}{Axiom}


\newcommand{\recn}[3]
{\setcounter{problemsetnum}{#1}
\handout{rec#1}{Notes for Recitation #1 (#2/98)}{#3}
}


\begin{document}

\recn{3}{2/20}{February 19, 1998, 2am}

\section{Buildup Error}

``Buildup error'' is a common source of mistakes in inductive proofs.
We saw an example in lecture yesterday.  Let's look at another example.

\begin{quotation}
\noindent {\bf False Theorem}: If every vertex in a vertex-colored simple
graph is adjacent to a vertex of the same color, then the graph is
monochromatic.
\end{quotation}

{\bf Class exercise}.  Exhibit a simple counter-example to this claim.

{\bf Solution}: A cycle on four vertices with two red vertices followed by
two blue vertices.  Each vertex is adjacent to some vertex of the same
color, but the graph is not monochromatic.


\medskip
(THIS IS PROOF IS PART OF THE TEAM PROBLEM HANDOUT.)

{\bf False Proof}: By induction on the number of vertices in the
graph.  Let $P(n)$ be the predicate, ``If every vertex in an $n$-vertex
vertex-colored simple graph is adjacent to a vertex of the same color,
then the graph is monochromatic.''

In the base case, $P(1)$, the graph contains only one vertex and so is
certainly monochromatic.

For the inductive step, we assume $P(n)$ in order to prove $P(n+1)$.  For
$n\geq 1$, let $G=(V,E)$ be a vertex-colored graph with $n+1$ vertices
such that every vertex is adjacent to a vertex of the same color, and let
$v \in V$ be an arbitrary vertex.  Let $G'$ be the subgraph of $G$
obtained by deleting $v$.  Since $G'$ is an $n$-vertex graph, we have by
induction that $G'$ is monochromatic.  By hypothesis, $v$ is adjacent to a
vertex $v'$ of the same color.  Since $v'$ must be a vertex of $G'$, it
follows that $v$ has the same color as all the other vertices.  Therefore,
$G$ is indeed monochromatic. \qed


{\bf Class Exercise}.  Pinpoint the flaw in this proof.

{\bf Solution}: the flaw is in the statement, ``Since $G'$ is an
$n$-vertex graph, we have by induction that $G'$ is monochromatic.''  This
is incorrect.  We can assume only that {\bf if} {\em every vertex in $G'$
is adjacent to a vertex of the same color}, {\bf then} we have by
induction that $G'$ is monochromatic.''  Unfortunately, removing $v$ from
$G$ may yield a $G'$ for which the adjacency condition fails.

\medskip
The correct assumption does not apply to $G'$ and does not lead to a
proof.  Of course a breakdown of the proof was inevitable, since the
theorem is false!

{\bf Class exercise}: Verify that the red/blue 4-cycle above is example
where the adjacency assumption fails for $G'$.

{\bf Solution}: We saw red/red/blue/blue 4-cycle satisfies the adjacency
condition.  Now remove, say, a red vertex.  Resulting graph red/blue/blue
graph leaves red vertex w/o a red neighbor.


\section{Well-Ordering}

There is another variation of induction that is sometimes useful:
well-ordering.  The well-ordering axiom looks nothing like the
induction axiom:

\begin{axiom}
Every nonempy set $S \subseteq \naturals$ has a smallest element.
\end{axiom}

The well-ordering axiom is often called the well-ordering
{\em principle}.  It may seem obvious and useless!

As for obvious, note that this axiom would be false if the set of
non-negative integers, $\naturals$, were replaced by, say, the set of
non-negative rational numbers; then for example the subset consisting of
the positive rational numbers has no smallest element.  It would also be
false if $\naturals$ was replaced by the set of {\em all} integers; then
the whole set has no least element.

As for useless, it may be surprising that everything that can be proven by
induction can also be proven using the well-ordering principle!  It's not
hard to prove this metamathetical fact, but we won't bother.  We'll just
illustrate a typical use of the Well-Ordering Principle.

Here is a special case of the {\em Principle of Inclusion-Exclusion}
which we'll take up in a few weeks.

\begin{theorem}
For all finite sets $A, B$
\[|A \cup B| = |A| + |B| - |A \cap B|. \]
\end{theorem}

Rosen, Section 1.5, Example 5 gives a simple explanation for this
equality: take the set $A \cup B$ and mark each element of $A$ and then
mark each element of $B$.  So the total number of marks is $|A|+|B|$.  The
elements in $A \cap B$ now wind up with two marks, while the others get
one mark.  If we now remove one mark from each element in $A \cap B$, we
are left with a total of $|A|+|B|- |A \cap B|$ marks.  Since each element
of $A\cup B$ is now left with exactly one mark, this last total must equal
$|A \cup B|$.

This is a pretty good argument which we would actuallly accept as a proof
later in the term---after we've had more experience recognizing when such
an argument can be reduced to careful reasoning about numbers, functions,
and sets.  But at this point in the term, the concepts of ``marking'' and
the rules for their bookkeeping remain too fuzzy for comfort.  So let's
prove the theorem with careful, elementary reasoning.

We'll need three simple facts relating set size to set operations in the
proof.
\begin{fact}
Any subset of a finite set is finite.
\end{fact}
\begin{fact}
$|A| = 0$ iff $A = \emptyset$.
\end{fact}
\begin{fact}
If $A$ is a finite set and $x \not \in A$, then $|A \cup \{x\}| = |A|
+ 1$.  In other words, if we add a new element to a set, it gets larger by
one.
\end{fact}
We could prove these three facts themselves from the definition of the
cardinality, $|A|$, of a finite set, $A$, using simple reasoning about
sets, but they are so simple and familiar that we'll take them for
granted.  (Definition 4 of Rosen, Section 1.4 claims to specify the
cardinality of a finite set, but it's not very crisp.  The precise
mathematical definition is that for $n \in \naturals, |A|$ is defined to
be $n$ iff there is a bijection from the integers $1,\dots, n$ to $A$.
And $A$ is {\em finite} iff $|A| = n$ for some $n \in \naturals$.)

{\em Proof by contradiction}: We will suppose the inclusion-exclusion
equality fails for some finite $A, B$ and reach a contradiction.

Suppose the equality fails for some finite $A, B$.  By Fact 1, $A - B$ is
also finite.  By the Well-Ordering Principle, there must therefore be
finite sets $A, B$ for which the equality fails and such that $|A - B|$ is
minimum among all such sets.

Note that by Fact 2, $|A - B| = 0$ iff $A - B = \emptyset$ iff $A
\subseteq B$.  But the inclusion-exclusion equality clearly holds when $A
\subseteq B$, so we conclude that $A - B \neq \emptyset$, that is, there
is some element $a \in A-B$.

Let $A' = A - \{a\}$.  From Fact 3
\[|A| = |A'| + 1.\]
Similarly, $A \cup B = (A' \cup B) \cup \{a\}$ and $a \not \in A' \cup B$,
so by Fact 3
\[|A \cup B| = |A' \cup B| + 1.\]
Likewise, $A - B = (A' - B) \cup \{a\}$ and $a \not \in A'-B$, so
\[|A - B| = |A' - B| + 1.\]
In particular, $|A' - B| < |A - B|$.  Finally, since $a \not \in B$, we
have that $A \cap B = A' \cap B$, so
\[|A \cap B| = |A' \cap B|.\]

Since $|A' - B| < |A - B|$ and $|A - B|$ was minimum for the equality to
fail, the equality must hold for $A', B$, that is,
\[|A' \cup B| = |A'| + |B| - |A' \cap B|. \]
Hence, 
\begin{eqnarray*}
|A \cup B| & = & |A' \cup B| +1\\
           & = & |A'| + |B| - |A' \cap B| +1\\
           & = & |A'| + 1 + |B| - |A \cap B|\\
           & = & |A| + |B| - |A \cap B|
\end{eqnarray*}
contradicting the fact that the equality fails for $A, B$. \qed

As we noted, Well-Ordering proofs can always be reformulated as proofs by
induction, and vice-versa.  In particular, the Well-Ordering proof above
can easily be transformed into a proof by induction on the size of $A-B$,
as the reader should check.


\section*{Team Problems}

\begin{problems}

\problem

How many simple graphs (up to isomorphism) are there with $|V| = |E| = 5$?


\problem

Let $A$ be the adjacency matrix for a digraph $G$ with $n$ vertices.  Note
that $A$ is a zero-one valued $n \times n$ matrix.  In this problem we use
the Boolean ``OR'' operation, $\vee$, instead of ``+'' when multiplying
zero-one valued matrices (this is called ``boolean'' matrix product).

\bparts

\ppart

For $k \in \naturals$, let $A^k$ be the $k$th {\em Boolean} power
of $A$.  Prove that ${A^k}_{ij} = 1$ iff there is a directed path of
length $k$ from the $i$th to the $j$th vertices of $G$.

\ppart

Let $B = A \vee I$ where $I$ is the $n \times n$ identity matrix.  Prove
that ${B^k}_{ij} = 1$ iff there is a directed path of length $\leq k$ from
the $i$th to the $j$th vertices of $G$.

\ppart 

Conclude that ${B^n}_{ij} = 1$ iff there is a directed path from the $i$th
to the $j$th vertex.

\eparts


\problem

The {\em complement}, $\overline G$, of a simple graph, $G$, is defined to
be the graph which has the same vertices as $G$ such that two vertices are
adjacent in $\overline G$ if and only if they are not adjacent in $G$.

\bparts

\ppart A subset, $A$, of the vertices of a simple graph, $G$, such that no
two vertices in $A$ are adjacent in $G$, is called an {\em anti-clique} of
$G$.  Prove that $G$ contains an anti-clique of size $m$ iff $\overline G$
contains a copy of $K_m$.

\ppart

A simple graph, $G$, is called {\em self-complementary} iff $G$ and
$\overline G$ are isomorphic.  Prove that if $G$ is a self-complementary
simple graph with $n$ vertices, then
\[n \equiv 0 \pmod{4}\mbox{   or   }n \equiv 1 \pmod{4}.\]
\hint How many edges altogether are there in $G$ and $\overline G$?

\ppart

For integer $n>0$, define a simple graph $G_n$ as follows: the vertices
are the integers $1,2,\dots,2n$.  Vertices $i \neq j$ are adjacent iff
$i,j \leq n$ or $(i \leq n \mbox{ and } j > n \mbox{ and } i \equiv j
\pmod{2})$.  

Prove that $G_n$ is not $(n-1)$-colorable.

\ppart

Prove that $G_n$ is self-complementary.
\eparts


\problem Let $G$ be a simple graph with $n>0$ vertices.  Prove that if $G$
has no vertex of degree $\geq m$, then $G$ has an anti-clique of size
$\geq n/m$.

\medskip
{\em Solution}: By strong induction on the number of vertices of $G$.

The base case $n \leq m$ follows by choosing the anti-clique to consist of
a single vertex.

So for the induction case, suppose $n > m$.  Pick any vertex of, $v$, of
$G$.  Remove $v$ and all vertices adjacent to $v$ from $G$; call the
remaining graph, $H$.  Now $H$ has at least $n - m$ vertices because $v$
has degree $< m$, and by definition of $H$, none of the vertices in $H$
are adjacent (in $G$) to $v$.  Since removing vertices does not increase
degrees, $H$ also has no vertex of degree $\geq m$.  By strong induction,
there is an anti-clique $A$ of $H$ of size at least $(n-m)/m = n/m - 1$.
So $A \cup \{v\}$ is an anti-clique of $G$ of size at least $n/m$. \qed


\bigskip
THE FOLLOWING PROBLEM WAS NOT USED.  IT'S MORE SUITABLE FOR LECTURE OR PSET
PRESENTATION.

\problem We have seen that both a graph and its complement may require a
lot of colors.  (In fact $G_n$ and hence $\overline G_n$ each contain a
copy of $K_n$, so neither is $(n-1)$-colorable.)

Is it possible to have a large graph such that {\em both} it and its
complement do {\em not} require a lot of colors?  A famous theorem of
Ramsey implies that this cannot happen---either the graph or its
complement must require a lot of colors.  More precisely,
\begin{quotation}

\noindent {\bf Theorem (Ramsey)}: Let $m$ and $l$ be positive integers,
and $G$ be a simple graph.  If $G$ has $\geq m^{l}$ vertices, then either
$G$ contains a copy of $K_l$ (and hence $G$ is not $l$ colorable) or
$\overline G$ contains $K_m$ (and hence $\overline G$ is not $m$
colorable).

\end{quotation}

Prove the Theorem.  \hint Induction on $l$.  There are two cases, (1) when
every vertex of $G$ has degree $< m^l$, or (2) when some vertex does have
degree $\geq m^l$.  The Lemma above handles case (1).

{\em Solution}:

The base case $l=1$ follows because $m^1 \geq 1$, and every graph with at
least one vertex has $K_1$ as a subgraph.

So assume that $G$ has at least $m^{l+1}$ vertices.  There are two cases:

(1) Every vertex of $G$ has degree $< m^l$.  Then by the Lemma, $G$ has an
anti-clique of size at least $m^{l+1}/m^l = m$, so $\overline G$ contains
$K_m$. \qed

(2) Some vertex, $v$, of $G$ has degree $> m^l$.  Let $H$ be the subgraph
obtained by restricting $G$ to the vertices adjacent to (and not
including) $v$.  Now $H$ has $\geq m^l$ vertices, so by induction,
either $H$ contains $K_l$ or $\overline H$ contains $K_m$.

Note that $\overline H$ is the restriction of $\overline G$ to the
vertices in $H$.  So if $\overline H$ contains a copy of $K_m$, so does
$\overline G$, and the Theorem holds.  Otherwise, $H$ contains a subgraph,
$C$, which is a copy of $K_l$.  So $C \cup \{v\}$ is the required copy of
$K_{l+1}$ in $G$. \qed

\end{problems}

\end{document}
