\documentclass[11pt]{article}
\include{/math/home/fac/saks/COMBNOTES/latexdefs}
%\usepackage{amsmath}
%\usepackage{amsfonts}
%\pagestyle{empty} %This determines whether the page number appears.
\topmargin -1.00in
\textheight 9in
\oddsidemargin 14pt
\evensidemargin 14pt
\textwidth 440pt
\addtolength{\parskip}{0.5\parskip}
%\newcommand{\binom}[2]{$\left( \begin{array}{c} 
%#1 \\ #2 \end{array} \right)$}
\newcommand{\nopar}{\hspace{-\parindent}}
\newcommand{\fsp}{\hspace{5em}}
\newcommand{\tsp}{\hspace{3em}}
\newcommand{\osp}{\hspace{1em}}
\newcommand{\Rl}{\bf R}
\newcommand{\remove}[1]{}
\begin{document}
\begin{flushleft}
{\large MATH 642:582--Fall, 2008} \\
{\bf Assignment 5--Due Wednesday December 17 noon (Version: December 15)} \\
\end{flushleft}

\parskip=10pt

A few preliminary remarks.
\begin{enumerate}
\item Follow the general instructions for homework given in: 

\begin{center}
http://www.math.rutgers.edu/~saks/homework.html
\end{center}
\item Please be on the look out for errors.  If something seems not
to make sense, check with me before investing a lot of time on the problem.

\end{enumerate}

\begin{center}
Problems to be handed in.
\end{center}

\begin{enumerate}

\item
Fix a positive integer $p$.  Find an exact expression for the number
of permutations of $[n]$ that have no cycle of length exactly $p$.
(Your expression will be a sum, but it 
should be as simple as possible).  Determine the asymptotics
of your expression as $n$ tends to $\infty$.

\item
\label{Jordan}
Let $A_1,\ldots,A_n$ be events in a probability space
and for $J \subseteq [n]$, let $A_J=\cap_{j \in J} A_j$.  Let
$p_J= \mathbf{Prob}[A_J]$.   
\begin{enumerate}
\item Determine (with proof) a function $c(n,t,j)$ (in as simple form
as possible) so that the probability that exactly
$t$ events occur is equal to $\sum_{J \subseteq [n]}
c(n,t,|J|) p_J$.
\item Let $T$ denote the random variable which is the number
of $A_j$ that occur.  Prove that for any real number $\alpha$,
${\mathbf E}[\alpha^T]=\sum_{J \subseteq [n]}p_J(\alpha-1)^{|J|}$.
\item Give a formula for the number of permutations of $[n]$ with
exactly $t$ fixed points, and determine the asymptotics (for fixed
$t$)  as $n$
tends to $\infty$. (This uses part (a) but not (b)).
\end{enumerate}

\item
\label{reconstruction}
In class it was shown that the edge-reconstruction conjecture
for graphs is true for all graphs $G$ with
$|E(G)| > \frac{1}{2}\binom{|V(G)|}{2}$.  In this problem, this result
will be extended to graphs for which 
$|E(G)| >1+ \log_2 (|V(G)|!)$.

More precisely,
let $n,m$ be fixed and consider 
graphs on vertex set $V=[n]$ having $m$ edges.  
Let $G_1$, $G_2$ be two graphs having $m$ edges
and let $E(G_1)=\{e_1,\ldots,e_m\}$
and $E(G_2)=\{f_1,\ldots,f_m\}$.
For $i \in \{1,2\}$ and $j \in [m]$, let $G_i^j=G_i-\{e_j\}$.
Assume that for all $j \in [m]$, $G_1^j$ is
isomorphic to $G_2^j$. The goal
is to prove: if $2^{m-1} > n!$
then $G_1$ is isomorpnic to $G_2$.

Suppose $\sigma$ is chosen uniformly at random
from the permutations of $[n]$.
Let $A_i$ (resp. $B_i$) be 
the event that $\sigma$ maps the endpoints of edge $e_i$ (resp. $f_i$)
to vertices that are not adjacent in $G_1$.
(Note: the lack of symmetry in these definitions
with respect to $G_1$ and $G_2$ is intentional.)

For $J \subseteq [m]$, let $A_J=\cap_{i \in J} A_i$
and $B_J=\cap_{i \in J}B_i$.  
For $0 \leq j \leq m$, let $a_j=\sum_{|J|=j} \mathbf{Prob}[A_J]$
and let $b_j=\sum_{|J|=j} \mathbf{Prob}[B_J]$

Let $Y$ denote the random variable that counts
the number of $i \in [m]$ such
that $A_i$ occurs and $Z$ denote the number of $i \in [m]$
such that $B_i$ occurs.

\begin{enumerate}
\item Show that if $a_j=b_j$ for all $j \in \{0,1,\ldots,m\}$
then $G_1$ is isomorphic to $G_2$.
\item Prove that if $G_1^k$ is isomorphic
to $G_2^k$ for all $k \in [m]$ then  for all $j \leq m-1$, $a_j=b_j$.
\item Prove that
$(b_m-a_m)=(-1/2)^{m}{\mathbf E}[(-1)^Y-(-1)^Z]$.  
\item 
Prove that if $2^{m-1} \geq n!$ then $b_m=a_m$.
\item Put the parts together to prove the theorem.
\end{enumerate}

Hints are given below.

\item
\begin{enumerate}
\item
Consider a probability space $\Omega$, and subsets (events) 
$A_1,A_2,\ldots, A_n$. As usual, for $I \subseteq [n]$, 
define $A_I=\cap_{i \in I} A_i$ and let
$p_I=\mathbf{Prob}[A_I]$.  Let $q_I=\mathbf{Prob}[A_I-\bigcup_{i \in [n]-[I]}A_i]$.
For each $I$, express $q_I$ in terms of $\{p_J:J \subseteq [n]\}$.

\item
Consider a finite probability space $\Omega$, and subsets (events) 
$A_1,A_2,\ldots, A_n$. As usual, for $I \subseteq [n]$, 
define $A_I=\cap_{i \in I} A_i$ and let
$p_I=\mathbf{Prob}[A_I]$.
Let $B_1,B_2, \ldots, B_n$ be another set of events
and define $q_I=\mathbf{Prob}[B_I]$.  Suppose that $p_I=q_I$ for all
$I \neq [n]$ but $p_{[n]} \neq q_{[n]}$.  Prove that  
$\Omega$ must have at least $2^{n-1}$ elements.
(Hint: Part (a) may be helpful.)
\item
Give an example to show that the bound in the first part is best
possible.
\end{enumerate}

\item A {\em Hamiltonian path} in a graph $G=(V,E)$ is a permutation
of the vertices $v_1,\ldots,v_n$ such that each pair
$v_i,v_{i+1}$ is adjacent in $G$ for $1 \leq i <n$.
A naive algorithm for testing whether a graph has a Hamiltonian
path requires checking all possible permutations of the
vertex set, and thus requires $n! poly(n)$ number of steps,
where $poly(n)$ denotes an unspecified polynomial function
of $n$.
The purpose of this problem is to derive an algorithm that
runs in $2^n poly(n)$ steps (and also requires memory
size only $poly(n)$).  
(Without being
too precise here about what a ``computation step''
is, we assume that adding, subtracting or multiplying
two $k$ bit numbers can be done in $poly(k)$ computation steps.)

\begin{enumerate}
\item A walk in a graph is a sequence $v_1,\ldots,v_k$
of vertices, possibly with repetition such that each
pair $v_i,v_{i+1}$ is adjacent in the graph.  For vertices
$x,y$ and integer $k$ let $W_G(x,y,k)$ denote the number
of $k$ step walks from $x$ to $y$.  Give a method for
computing $W_G(x,y,k)$ that uses at most $poly(n,k)$ steps.
\item
Let $H_G(x,y)$ denote the number of Hamiltonian paths in $G$.
Use the answer to the previous problem and inclusion-exclusion
to derive a formula for computing $H_G(x,y)$ that
uses at most $2^n poly(n)$ computation steps.  
\end{enumerate}

\item 
\label{chromatic}
In this problem, we'll show that the chromatic
number of an $n$-vertex graph can be computed 
in time $2^n poly(n)$.

Let $G$ be a given graph on vertex set $V$, with $|V|=n$.

\begin{enumerate}
\item Let $f:2^V \longrightarrow \{0,1\}$ be the function with
$f(W)=1$ if and only if $W$ is independent.  Describe how
to construct a function table for $f$ in time $poly(n)2^n$.
\item 
For $0 \leq i \leq n$,
define functions $f_i:2^V \longrightarrow \mathbb{N}$
by: $f_0=f$ and for $1 \leq i \leq n$, and for $W \subseteq V$,
$f_i(W)=f_{i-1}(W)$ if $i \not\in W$ and
$f_i(W)=f_{i-1}(W)+f_{i-1}(W-\{i\})$ if $i \in W$.
Let $g=f_n$.
Prove that $g(W)$ is equal to the number of subsets of $W$ that
are independent
sets of $G$.  Also, show that a table
for $g$ can be constructed in time $poly(n)2^n$.
\item
Let $c_k(G)$ denote the number of sequences $I_1,\ldots,I_k$
of $k$ independent sets whose union is $V$.
Express $c_k(G)$ in terms of the function values of
the function $g$ defined in the previous part.
\item
Explain how to compute the chromatic number of $G$ using
at most $poly(n)2^n$ arithmetic operations.
\end{enumerate}


\end{enumerate}



\begin{center}
{\bf Some hints}
\end{center}
\begin{description}
\item[Problem \ref{reconstruction}] 
For part (a): Use inclusion exclusion to express the probability
that $\sigma$ is an isomorphism from $G_1$ to itself, and
to express the probability that $\sigma$ is an isomorphism
from $G_1$ to $G_2$.

For part (c): use the second part of problem \ref{Jordan}.

\item[Problem \ref{chromatic}]
For part (c), for each vertex $v$, let $A_v$ be the $k$-tuples
$I_1,\ldots,I_k$ for which $v$ belongs to none of the sets $I_j$
and use inclusion-exclusion.
\end{description}







\end{document}