\documentstyle[12pt,amssymb,amstex,twoside]{article}
\input{macros-course}

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{5}{October 03, 1995}{Start of Class, October 17}

{\bf Reading:} Sections 6.6, 7.1--7.5, and 7.8 of {\it
Discrete Mathematics and its Applications} by Kenneth H. Rosen.

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
What does the Hasse diagram look like for a totally ordered set on $n$
elements. Prove your answer. (Hint: use induction and the lemma about
the existence of a minimal element in any poset, that was proved in
class.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Consider a poset of $N$ tasks such that the length of the longest chain is $D$. You have $P$ processors on which to execute these tasks. Each task takes one unit of time to execute on a processor.
\bparts
\ppart Show that $D$ is a lower bound on the number of time units needed to execute all the tasks.
\ppart Show that $N/P$ is also a lower bound on the number of time units needed to execute all the tasks.
\ppart Show that all the tasks can be executed in time $D + N/P$. (Hint: consider a partition of the poset into $D$ antichains.)
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\bparts
\ppart
A set of circles on the plane is said to be {\em good} if for any pair
of circles one is contained within the other. A set of circles on the
plane is said to be {\em bad} if for any pair of circles neither one
is contained within the other.  Show that in any collection of $N$
circles there is a subset of $\sqrt{N}$ circles which is good or bad. 
\ppart A set of natural numbers is said to be {\em good} if for any pair
of numbers one divides the other. A set of natural numbers is said to be {\em bad} if for any pair
of numbers neither one divides the other.  Show that in any collection of $N$
numbers there is a subset of $\sqrt{N}$ numbers which is good or bad.

(Note: if you plan to use a theorem about posets make sure to prove that the structure in question is in fact a poset.)
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\vspace*{1in}



Consider the graph above.
\bparts
\ppart How many connected components does it have?
\ppart List all the nodes in the graph along with their associated degrees.
\ppart For each pair of vertices consider the number of paths of length $3$ between them and represent this data in the form of a matrix. What relationship does this matrix bear to the adjacency matrix of the graph?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
A graph is said to be bipartite if it is $2$-colorable. Show that every tree is bipartite. (Hint: first show that every tree has a leaf.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
What is wrong with the following ``theorem'' and ``proof?''\\
{\em False theorem:} If every vertex in a graph has degree at least one then the graph is connected.\\
{\em False proof:} We prove the result by induction on the number of vertices. Let $P(n)$ be ``if every vertex in a graph with $n$ vertices has degree at least one then the graph is connected.''\\
Base case. $P(2)$ is true since the only graph satisfying the assumption is that with two vertices and one edge between them which is easily seen to be connected.\\
Inductive step. Assume $P(n)$ is true. Now, take any graph on $n$ vertices with minimum degree at least one and add a new vertex to it. By inductive hypothesis the graph on $n$ vertices is connected. Since the new vertex satisfies the assumption it must have degree at least one, so it must have an edge connecting it to one of the remaining $n$ vertices. Thus the whole graph is connected. Hence $P(n+1)$ is true. Thus, $P(n)$ is true for all $n$.





%A graph is said to be planar if it can be drawn on the plane so that edges do not cross each other. Take the following fact for granted:  every planar graph contains at least one node of degree at most $5$. Now prove that any planar graph can be $6$-colored.


\end{problems} 

\end{document}




