\documentclass[11pt]{amsart}

\usepackage{amsmath,amsthm,amssymb}
\usepackage{stmaryrd}

\usepackage{fancyhdr} % Allows customization of verbatim environments

\usepackage{xcolor}

%\usepackage[textheight=8.5in, margin=1.6in]{geometry}
\usepackage[
  hmarginratio={1:1},     % equal left and right margins
%  vmarginratio={1:1},     % equal top and bottom margins
  %textwidth=400pt,        % new text width
  heightrounded,          % always useful
  %bindingcorrection=5mm,  % binding correction
  total={6in,8in}
]{geometry}
\headheight=13pt
\footskip=13pt

\usepackage{needspace}  % <-- to prevent bad pagebreak over environment titles
% Use:  \Needspace{3\baselineskip} before opening an environment

\usepackage{graphicx}

% Tikz stuff.
\usepackage{tikz}
%\usepackage{tkz-graph}
\usepackage{pgfplots}
%\usepackage{tikz-3dplot}
\pgfplotsset{compat=newest}
%\usepgfplotslibrary{fillbetween}
%\usetikzlibrary{cd}
%\usetikzlibrary{positioning}
%\usetikzlibrary{decorations.pathmorphing}    
%\usetikzlibrary{decorations.pathreplacing}
%\usetikzlibrary{arrows.meta,calc}
%\usetikzlibrary{bending}
%\usetikzlibrary{decorations.markings,shapes.geometric}
%\tikzset{->-/.style={decoration={markings, mark=at position #1 with
%  {\arrow{>}}},postaction={decorate}}}
%\tikzset{-|-/.style={decoration={markings, mark=at position #1 with
%  {\arrow{stealth}}},postaction={decorate}}}
%\tikzset{movearrow/.style 2 args ={
%        decoration={markings,
%	  mark= at position {#1} with {\arrow{#2}} ,
%        },
%        postaction={decorate}
%    }
%}
%\tikzset{<--/.style={decoration={markings, mark=at position #1 with
%  {\arrow{<}}},postaction={decorate}}}
\tikzstyle{ball} = [circle,shading=ball, ball color=black,
    minimum size=1mm,inner sep=1.3pt]
%\tikzstyle{bball} = [circle,shading=ball, ball color=blue,
%    minimum size=1mm,inner sep=1.3pt]
%\tikzstyle{miniball} = [circle,shading=ball, ball color=black,
%    minimum size=1mm,inner sep=0.5pt]
%\tikzstyle{redminiball} = [circle,shading=ball, ball color=red,
%    minimum size=1mm,inner sep=0.5pt]
%\tikzstyle{mminiball} = [circle,shading=ball, ball color=black,
%    minimum size=0.6mm,inner sep=0.1pt]
%\tikzstyle{mycircle} = [draw,circle, minimum size=1mm,inner sep=1.3pt]
%\newcommand*{\DashedArrow}[1][]{\mathbin{\tikz [baseline=-0.25ex,-latex, dashed,#1] \draw [#1] (0pt,0.5ex) -- (1.3em,0.5ex);}}%

%%%% tikz style for finite automata
\usetikzlibrary{automata, positioning, arrows}
\tikzset{fa/.style={
    ->, % makes the edges directed
    >=stealth, % makes the arrow heads bold
    node distance=2cm, % specifies the minimum distance between two nodes. Change if necessary.
    every state/.style={thick, fill=gray!10}, % sets the properties for each ’state’ node
    initial text=$ $, % sets the text that appears on the start arrow
}}
%%%%

\usepackage{needspace}  % <-- to prevent bad pagebreak over environment titles
% Use:  \Needspace{3\baselineskip} before opening an environment

\usepackage[shortlabels]{enumitem}
\setlist[enumerate]{itemsep=4pt,leftmargin=*,label={(\alph*)},topsep=4pt}
%\setlist[enumerate]{itemsep=2pt,label={\arabic*.}}

\usepackage[T1]{fontenc}
\renewcommand{\labelitemi}{\guillemotright}

\allowdisplaybreaks

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\W}{\mathbb{W}}
\newcommand{\KK}{\Bbbk}
\newcommand{\ve}{\varepsilon}
\newcommand{\scribe}{
  \begin{center}%
    Scribe~$=$ \rule{7cm}{0.15mm}%
  \end{center}%
  \medskip%
}
\DeclareMathOperator{\im}{\mathrm{im}}
\DeclareMathOperator{\id}{\mathrm{id}}
\DeclareMathOperator{\glb}{\mathrm{glb}}
\DeclareMathOperator{\lub}{\mathrm{lub}}

\newcounter{problem}
\renewcommand \thesection {\theproblem}
\newenvironment{prob}[1][]
{
\refstepcounter{problem}\par\medskip
\def\myArg{#1}
  \ifx\myArg\empty
    \noindent \textsc{Problem~\theproblem.} \rmfamily
  \else
    \noindent \textsc{Problem~\theproblem\ (\textnormal{#1}).} \rmfamily
  \fi
}
{
\medskip

}

\newenvironment{sol}
{\emph{Solution.}
}
{
  \medskip

}

\parskip = 0.05in
\parindent = 0.0in
\raggedbottom

%\pagestyle{empty}
%\pagenumbering{gobble}

\fancypagestyle{firststyle}
{
\fancyhead[L,LO]{
\textit{\small Math 387 Group problems, Wednesday Week 12}
}
\renewcommand{\headrulewidth}{0pt}
}

\begin{document}
\thispagestyle{firststyle}
\bigskip

\begin{prob} Review.
  What does it mean for a language~$A$ to be in IP? Review the conditions
  for when~$w\in A$ and $w\not\in A$.
\end{prob}

\begin{prob}
  Explain why~$\text{NP}\subseteq \text{IP}$.  Is it the case that~$\text{NP}=\text{IP}$? 
\end{prob}

\begin{prob}
  Let 
  \[
    \text{ISO}=\{\langle G,H\rangle: \text{$G$ and~$H$ are isomorphic
    graphs}\}.
  \]
  Explain why $\text{ISO}\in \text{IP}$.
\end{prob}

\begin{prob}
  Determine which pairs of the following are isomorphic, if any.
      \begin{center}
        \begin{tikzpicture}[scale=0.3]
  	\begin{scope}
  	  \node[ball,label={left:$a$}] at (-1,-1) (a) {};
  	  \node[ball,label={right:$b$}] at (1,-1) (b) {};
  	  \node[ball,label={right:$c$}] at (1,1) (c) {};
  	  \node[ball,label={left:$d$}] at (-1,1) (d) {};
  	  \node[ball,label={left:$e$}] at (-3,-3) (e) {};
  	  \node[ball,label={right:$f$}] at (3,-3) (f) {};
  	  \node[ball,label={right:$g$}] at (3,3) (g) {};
  	  \node[ball,label={left:$h$}] at (-3,3) (h) {};
  	  \draw (a)--(b)--(c)--(d)--(a);
  	  \draw (e)--(f)--(g)--(h)--(e);
  	  \draw (a)--(e);
  	  \draw (b)--(f);
  	  \draw (c)--(g);
  	  \draw (d)--(h);
  	\end{scope}
  	\begin{scope}[xshift=12cm]
  	  \node[ball,label={left:$\alpha$}] at (-2,3) (a) {};
  	  \node[ball,label={left:$\beta$}] at (-2,1) (b) {};
  	  \node[ball,label={left:$\gamma$}] at (-2,-1) (c) {};
  	  \node[ball,label={left:$\delta$}] at (-2,-3) (d) {};
  	  \node[ball,label={right:$\epsilon$}] at (2,3) (e) {};
  	  \node[ball,label={right:$\zeta$}] at (2,1) (f) {};
  	  \node[ball,label={right:$\eta$}] at (2,-1) (g) {};
  	  \node[ball,label={right:$\theta$}] at (2,-3) (h) {};
  	  \draw (a)--(f);
  	  \draw (a)--(g);
  	  \draw (a)--(h);
  	  \draw (b)--(e);
  	  \draw (b)--(g);
  	  \draw (b)--(h);
  	  \draw (c)--(e);
  	  \draw (c)--(f);
  	  \draw (c)--(h);
  	  \draw (d)--(e);
  	  \draw (d)--(f);
  	  \draw (d)--(g);
  	\end{scope}
  	\begin{scope}[xshift=24cm,scale=1.6]
  	  \foreach \t in {0,...,7} {
  	    \node[ball,label={45*\t:\t}] at (45*\t:2) (\t) {};
  	  };
  	  \draw (0)--(1)--(2)--(3)--(4)--(5)--(6)--(7)--(0);
  	  \draw (0)--(4);
  	  \draw (1)--(5);
  	  \draw (2)--(6);
  	  \draw (3)--(7);
  	  \draw (0)--(4);
  	  \draw (1)--(5);
  	  \draw (2)--(6);
  	  \draw (3)--(7);
  	\end{scope}
        \end{tikzpicture}
      \end{center}
\end{prob}

\begin{prob}  Here we describe an efficient algorithm for determining whether
  two trees are isomorphic.  We start with a labeling system for rooted trees,
  i.e., pairs $(T,r)$ where~$T$ is a tree and~$r$ is a fixed vertex of~$T$.
  We recursively assign a label to $T$ consisting of a balanced parenthetical
  expression as follows:
  \begin{enumerate}[1.]
    \item Leaf nodes are assigned the label~$()$.
    \item Every time we move up a level (in towards the root), label the vertex
      by listing the labels of its subtrees, sorted lexicographically by
      increasing size, and
      surround the resulting sorted list by $()$.
    \item A vertex cannot be labeled until all of its children are labeled.
  \end{enumerate}
  It turns out that two rooted trees are isomorphic if and only if there roots
  have the same labels.
  \begin{enumerate}
    \item  Apply the labeling to the two rooted trees listed below:
      \begin{center}
        \begin{tikzpicture}
          \node[ball] at (0,0) (a) {};
          \node[ball] at (-1,-1) (b) {};
          \node[ball] at (1,-1) (c) {};
          \node[ball] at (2.5,-1) (d) {}; 
	  \draw (a)--(b);
	  \draw (a)--(c);
	  \draw (a)--(d);
          \node[ball] at (-1.5,-2) (e) {};
          \node[ball] at (-0.5,-2) (f) {};
	  \draw (b)--(e);
	  \draw (b)--(f);
          \node[ball] at (0.5,-2) (g) {};
          \node[ball] at (1.5,-2) (h) {};
	  \draw (c)--(g);
	  \draw (c)--(h);
          \node[ball] at (2.5,-2) (i) {}; 
	  \draw (d)--(i);
          \node[ball] at (-2,-3) (j) {};
          \node[ball] at (-1,-3) (k) {};
	  \draw (e)--(j);
	  \draw (e)--(k);
          \node[ball] at (-0.5,-3) (l) {};
	  \draw (f)--(l);
          \node[ball] at (0.5,-3) (m) {};
	  \draw (g)--(m);
	  \begin{scope}[xshift=7cm]
	    \node[ball] at (0,0) (n) {};
	    \node[ball] at (-1,-1) (o) {};
	    \node[ball] at (1,-1) (p) {};
	    \node[ball] at (2.5,-1) (q) {}; 
	    \draw (n)--(o);
	    \draw (n)--(p);
	    \draw (n)--(q);
	    \node[ball] at (-1.5,-2) (r) {};
	    \node[ball] at (-0.5,-2) (s) {};
	    \draw (o)--(r);
	    \draw (o)--(s);
	    \node[ball] at (1,-2) (t) {};
	    \draw (p)--(t);
	    \node[ball] at (2,-2) (u) {};
	    \node[ball] at (3,-2) (v) {};
	    \draw (q)--(u);
	    \draw (q)--(v);
	    \node[ball] at (-0.5,-3) (w) {};
	    \draw (s)--(w);
	    \node[ball] at (2,-3) (x) {};
	    \draw (u)--(x);
	    \node[ball] at (2.5,-3) (y) {};
	    \node[ball] at (3.5,-3) (z) {};
	    \draw (v)--(y);
	    \draw (v)--(z);
	  \end{scope}
        \end{tikzpicture}
      \end{center}
    \item What is the runtime of this algorithm, in general?
    \item For the case of unrooted trees, we first define the \emph{center} of a tree.
      The center is a either a vertex or a pair of vertices found by first
      coloring all of the leaf vertices.  The uncolored vertices form a tree.
      Color its vertices.  Repeat until there are at most two vertices remaining.
      Find the center of the tree on the left in the previous part of this
      problem.
    \item Describe how to use the idea of a center of a tree to solve the
      isomorphism problem for trees (unrooted) in polynomial time.
  \end{enumerate}
\end{prob}

\begin{prob} (bonus)
    Fix a set of $k$ colors, $C=\{0,1,\ldots,k-1\}$.  A \emph{$C$-colored
    graph} is a finite directed simple graph $G$ in which each vertex is
    assigned a color in~$C$.  Two such graphs are isomorphic if there is a graph
    isomorphism between them (i.e., a bijection~$\phi$ of the vertices
    inducing a bijection of the edges) that preserves vertex color (i.e., if a
    vertex $v$ has color~$j$, then so does vertex~$\phi(v)$).  Consider the
    language
    \[
      \text{COL-ISO} = \{\langle G,H\rangle: \text{$G$ and~$H$ are isomorphic
      $C$-colored graphs}\}.
    \]
    Show that
    \[
      \text{COL-ISO}\leq_{P} \text{ISO},
    \]
    where ISO is the language corresponding to the usual (non-colored) graph
    isomorphism problem.
\end{prob}

\end{document}
