% 
% LaTeX Problem Set Template by Sachin Padmanabhan
% I created this when I was a freshman in CS 103,
% and I continue to use it to this day.
%
% Hope you enjoy!
%
% There may be problems with this template.
% If so, feel free to contact me.
%

% Updated for Fall 2018 by Michael Zhu

\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage[margin=1in]{geometry}
\usepackage{multicol}
\usepackage{bm}
\usepackage{listings}
\PassOptionsToPackage{usenames,dvipsnames}{color}  %% Allow color names
\usepackage{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{wrapfig}
\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=blue,
}
\usepackage{mathrsfs}

\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#4}
\author{Your Name(s) Here}
\date{\today}

\lhead{Your Name(s) Here}
\chead{Problem Set \#4}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Autumn 2018}
\rfoot{\thepage}

\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\absfit}[1]{\left\lvert #1 \right\rvert}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\eval}[3]{\left[#1\right]_{#2}^{#3}}
\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\pd}[1]{\frac{\partial}{\partial #1}}
\newcommand{\inner}[1]{\langle#1\rangle}
\newcommand{\cond}{\bigg|}
\newcommand{\rank}[1]{\mathbf{rank}(#1)}
\newcommand{\range}[1]{\mathbf{range}(#1)}
\newcommand{\nullsp}[1]{\mathbf{null}(#1)}
\newcommand{\repr}[1]{\left\langle#1\right\rangle}

\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Tr}{\mathbf{Tr}}
\DeclareMathOperator{\diag}{\mathbf{diag}}
\DeclareMathOperator{\dist}{\mathbf{dist}}
\DeclareMathOperator{\prob}{\mathbf{prob}}
\DeclareMathOperator{\dom}{\mathbf{dom}}
\DeclareMathOperator{\E}{\mathbf{E}}
\DeclareMathOperator{\Q}{\mathbb{Q}}
\DeclareMathOperator{\R}{\mathbb{R}}
\DeclareMathOperator{\var}{\mathbf{var}}
\DeclareMathOperator{\quartile}{\mathbf{quartile}}
\DeclareMathOperator{\conv}{\mathbf{conv}}
\DeclareMathOperator{\VC}{VC}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator{\Ber}{Bernoulli}
\DeclareMathOperator{\NP}{\mathbf{NP}}
\DeclareMathOperator{\coNP}{\mathbf{coNP}}
\DeclareMathOperator{\TIME}{\mathsf{TIME}}
\DeclareMathOperator{\polytime}{\mathbf{P}}
\DeclareMathOperator{\PH}{\mathbf{PH}}
\DeclareMathOperator{\SIZE}{\mathbf{SIZE}}
\DeclareMathOperator{\ATIME}{\mathbf{ATIME}}
\DeclareMathOperator{\SPACE}{\mathbf{SPACE}}
\DeclareMathOperator{\ASPACE}{\mathbf{ASPACE}}
\DeclareMathOperator{\NSPACE}{\mathbf{NSPACE}}
\DeclareMathOperator{\Z}{\mathbb{Z}}
\DeclareMathOperator{\N}{\mathbb{N}}
\DeclareMathOperator{\EXP}{\mathbf{EXP}}
\DeclareMathOperator{\NEXP}{\mathbf{NEXP}}
\DeclareMathOperator{\NTIME}{\mathbf{NTIME}}
\DeclareMathOperator{\DTIME}{\mathbf{DTIME}}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\BPP}{\mathbf{BPP}}
\DeclareMathOperator{\ZPP}{\mathbf{ZPP}}
\DeclareMathOperator{\RP}{\mathbf{RP}}
\DeclareMathOperator{\coRP}{\mathbf{coRP}}
\DeclareMathOperator{\BPL}{\mathbf{BPL}}
\DeclareMathOperator{\IP}{\mathbf{IP}}
\DeclareMathOperator{\PSPACE}{\mathbf{PSPACE}}
\DeclareMathOperator{\NPSPACE}{\mathbf{NPSPACE}}
\DeclareMathOperator{\SAT}{\mathsf{SAT}}
\DeclareMathOperator{\NL}{\mathbf{NL}}
\DeclareMathOperator{\PCP}{\mathbf{PCP}}
\DeclareMathOperator{\PP}{\mathbf{PP}}
\DeclareMathOperator{\cost}{cost}
\let\Pr\relax
\DeclareMathOperator*{\Pr}{\mathbf{Pr}}

\definecolor{shadecolor}{gray}{0.9}

\theoremstyle{plain}
\newtheorem*{lem}{Lemma}

\theoremstyle{plain}
\newtheorem*{claim}{Claim}

\theoremstyle{definition}
\newtheorem*{answer}{Answer}

\newtheorem{theorem}{Theorem}[section]
\newtheorem*{thm}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\setlength{\parindent}{0pt}

\pagestyle{fancy}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

% start MZ
\usetikzlibrary{automata,positioning}
\let\oldemptyset\emptyset
\renewcommand{\emptyset}{\text{\O}}
\renewcommand\qedsymbol{$\blacksquare$}
\newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol}
\renewcommand{\emph}[1]{\textit{\textbf{#1}}}
\newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}}
\usepackage{stmaryrd}
\usepackage{minted}
\usepackage{mathtools}
% end MZ

\begin{document}

\maketitle

\section{Cartesian Products and Set Cardinalities}

If $A$ and $B$ are sets, the \textbf{\textit{Cartesian product}} of $A$ and $B$, denoted $\mathbf{A \times B}$, is the set

\begin{equation*}
\{ (x, y)\ |\ x \in A \land y \in B \}
\end{equation*}

Intuitively, $A \times B$ is the set of all ordered pairs you can make by taking one element from $A$ and one element from $B$, in that order. For example, the set $\{\textcolor{red}{1}, \textcolor{red}{2}\} \times \{\textcolor{blue}{u}, \textcolor{blue}{v}, \textcolor{blue}{w}\}$ is

\begin{equation*}
\{\ (\textcolor{red}{1}, \textcolor{blue}{u}), (\textcolor{red}{1}, \textcolor{blue}{v}), (\textcolor{red}{1}, \textcolor{blue}{w}), (\textcolor{red}{2}, \textcolor{blue}{u}), (\textcolor{red}{2}, \textcolor{blue}{v}), (\textcolor{red}{2}, \textcolor{blue}{w})\ \}
\end{equation*}

For the purposes of this problem, let's let $\bigstar$ and $\smiley{}$ denote two arbitrary objects where $\bigstar \ne \smiley{}$. Over the course of this problem, we're going to ask you to prove that $|\N \times \{\bigstar, \smiley{}\}| = |\N|$. 

\begin{enumerate}[label*=\roman*.,ref=\roman*]
    \item Draw a picture showing a way to pair of the elements of $\N \times \{\bigstar, \smiley{}\}$ with the elements of $\N$ so that no elements of either set are uncovered or paired with multiple elements.
    
    \annotate{You might want to draw some pictures of the set $\N \times \{\bigstar, \smiley{}\}$ so that you can get a better visual intuition.}
    \begin{shaded}
    Place your picture here.
    \end{shaded}
    
    \item Based on the picture you came up with in part (i),
    define a bijection $f : \N \times \{\bigstar, \smiley{}\} \to \N$. The inputs
    to this function will be elements of $\N \times \{\bigstar, \smiley{}\}$, so you can define your function by writing
    \begin{shaded}
    \begin{center}
    $f(n, x) = $  \underline{\hspace{35ex}} % Write you definition here
    \end{center}
    \end{shaded}
    where $n \in \N$ and $x \in \{\bigstar, \smiley{}\}$. 
    
    \annotate{In defining this function, you cannot assume $\bigstar$ or $\smiley{}$ are numbers, since they're arbitrary values out of your control. See if you can find a way to define this function that doesn't treat $\bigstar$ or $\smiley{}$ algebraically.}
    
    \item Prove that the function you came up with in part (ii) is a bijection.
    \begin{shaded}
    Provide a proof here.
    \end{shaded}

\end{enumerate}

The result you've proved here essentially shows that $2\aleph_0 = \aleph_0$. Isn't infinity weird?

\pagebreak

\section{Understanding Diagonalization}

Proofs by diagonalization are tricky and rely on nuanced arguments. In this problem, we'll ask you to review formal proof of Cantor's theorem to help you better understand how it works. \\
(Please read the Guide to Cantor's Theorem before attempting this problem.)

\begin{enumerate}[label*=\roman*.,ref=\roman*]
    \item Consider the function $f : \N \to \wp(\N)$ defined as $f(n) = \varnothing$. Trace through our proof of Cantor's theorem with this choice of $f$ in mind. In the middle of the argument, the proof defines some set $D$ in terms of $f$. Given that $f(n) = \varnothing$, what is that set $D$? Provide your answer without using set-builder notation. Is it clear why $f(n) \neq D$ for any $n \in \N$?
    
    \annotate{Make sure you can determine what the set D is both by using the visual intuition behind Cantor's theorem
    and by symbolically manipulating the formal definition of D given in the proof.}
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
    
    \item Let $f$ be the function from part (i). Find a set $S \subseteq \N$ such that $S \neq D$, but $f(n) \neq S$ for any $n \in \N$. Justify your answer. This shows that while the diagonalization proof will always find \textit{some} set $D$ that isn't covered by $f$, it won't find \textit{every} set with this property.
    
    \begin{shaded}
    Write your answer here and justification here.
    \end{shaded}
    
    \item Repeat part (i) of this problem using the function $f : \N \to \wp(\N)$ defined as 
    $$f(n) = \{ m \in \N \mid m \geq n \}$$ 
    Now what do you get for the set $D$? Is it clear why $f(n) \neq D$ for any $n \in \N$?
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
    
    \item Repeat part (ii) of this problem using the function $f$ from part (iii).
    
    \begin{shaded}
    Write your answer and justification here.
    \end{shaded}
    
    \item Give a function $f : \N \rightarrow \wp(\N)$ such that the set $D$ obtained from the proof of Cantor's theorem is the set $\{ n \in \N \mid n$ is even\}. Briefly justify your answer.
    
    \begin{shaded}
    Write your answer and justification here.
    \end{shaded}

\end{enumerate}

\pagebreak

\section{Simplifying Cantor's Theorem?}

Below is a purported proof that $|S| \neq |\wp(S)|$ that doesn't use a diagonal argument:

\vspace{-2em}
\begin{quote}
\begin{thm}
If $S$ is a set, then $|S| \neq |\wp(S)|$.
\end{thm}
\begin{proof}
Let $S$ be any set and consider the function $f : S \to \wp(S)$ defined as $f(x) = \{x\}$. To see that this is a valid function from $S$ to $\wp(S)$, note that for any $x \in S$, we have $\{x\} \subseteq S$. Therefore, $\{x\} \in \wp(S)$ for any $x \in S$, so $f$ is a legal function from $S$ to $\wp(S)$. \\

Let's now prove that $f$ is injective. Consider any $x_1, x_2 \in S$ where $f(x_1) = f(x_2)$. We'll prove that $x_1 = x_2$. Because $f(x_1) = f(x_2)$, we have $\{x_1\} = \{x_2\}$. Since two sets are equal if and only if their elements are the same, this means that $x_1 = x_2$, as required. \\

However, $f$ is not surjective. Notice that $\varnothing \in \wp(S)$, since $\varnothing \subseteq S$ for any set $S$, but that there is no $x$ such that $f(x) = \varnothing$; this is because $\varnothing$ contains no elements and $f(x)$ always contains one element. Since $f$ is not surjective, it is not a bijection. Thus $|S| \neq |\wp(S)|$.
\end{proof}
\end{quote}

Unfortunately, this proof is incorrect. What's wrong with this proof? Justify your answer by pointing to a specific claim that's made here that's incorrect and explaining why it's incorrect.

\begin{shaded}
Write your answer and justification here.
\end{shaded}

\pagebreak

\section{Paradoxical Sets}

What happens if we take \textit{everything} and throw it into a set? If we do, we would get a set called the \emph{universal set}, which we denote $\mathscr{U}$:
$$\mathscr{U} = \{ x \mid \text{$x$ exists} \}$$
Absolutely everything would belong to this set: we'd have $1 \in \mathscr{U}$, $\N \in \mathscr{U}$, $\text{CS103} \in \mathscr{U}$, $\text{whimsy} \in \mathscr{U}$, etc.

In fact, we'd even have $\mathscr{U} \in \mathscr{U}$, which is strange but not immediately a problem. \\

Unfortunately, the set $\mathscr{U}$ doesn't actually exist, as its existence would break mathematics.

\begin{enumerate}[label*=\roman*.,ref=\roman*]
    \item Prove that if $A$ and $B$ are arbitrary sets where
    $A \subseteq B$, then $|A| \leq |B|$.
    
    \annotate{Look at the Guide to Cantor's Theorem. Formally speaking, if you want to prove that $|A| \leq |B|$, what do you need to prove? Your answer should involve defining some sort of function between $A$ and $B$ and proving that function has some specific property or properties.}
    
    \begin{shaded}
    Provide a proof here.
    \end{shaded}
    
    \item Using your result from (i),
    prove that if $\mathscr{U}$ exists, then
    $|\wp(\mathscr{U})| \leq |\mathscr{U}|$.
    \begin{shaded}
    Provide a proof here.
    \end{shaded}
    
    \item The \emph{Cantor-Bernstein-Schroeder Theorem} says that if $A$ and $B$ are sets such that $|A| \le |B|$ and $|B| \le |A|$, then $|A| = |B|$. Using the Cantor-Bernstein-Schroeder Theorem and the formal definitions of the different cardinality relations, prove that if $A$ and $B$ are sets where $|A| \le |B|$, then $|B| \not< |A|$.
    
    \annotate{In this proof you're essentially showing that the $\le$ and $<$ relations involving set cardinality work like the $\le$ and $<$ relations over regular numbers. Since the goal of the proof is to show that these cardinality relations work like regular inequality symbols, this result isn't ``obvious'' and you'll need to use formal definitions.} \\
    \annotate{Be careful not to use relations we haven't defined. For example, we know that $|A| < |B|$ means because we have a definition for it in terms of bijections and injections. We don't, however, have a definition of what $|A| > |B|$ means, so you should not use that notation in your solution (after all, we don't know what it means!) In particular, make sure not to assume that the negation of $|A| \leq |B|$ is $|A| > |B|$, since we don't have any reason to believe this.}
    
    \begin{shaded}
    Provide a proof here.
    \end{shaded}
    
    \item Using your result from parts (i), (ii), and (iii) of this problem, prove that $\mathscr{U}$ does not exist.
    
    \begin{shaded}
    Provide a proof here.
    \end{shaded}

\end{enumerate}

The result you've proven shows that there is a collection of objects (namely, the collection of everything that exists) that cannot be put into a set (whoa!!). When this was discovered at the start of the twentieth century, it caused quite a stir in the mathematical world and led to a reexamination of logical reasoning itself and a more formal definition of what objects can and cannot be gathered into a set. If you're curious to learn more about what came out of that, take Math 161 (Set Theory) or Phil 159 (Non-Classical Logic).

\pagebreak

\section{Avoiding Sampling Bias with Independent Sets}

An \textbf{\textit{independent set}} in a graph $G = (V, E)$ is a set $I \subseteq V$ with the following property: 
$$\forall u \in I.\ \forall v \in I.\ \{u, v\} \not\in E.$$
This question explores independent sets and their properties.

\begin{enumerate}[label*=\roman*.,ref=\roman*]
    \item Explain what an independent set is in plain English and without making reference to first-order logic. No justification is necessary.
    
    \annotate{You may want to draw some pictures of graphs to see what independent sets look like. Don't just come up with a literal translation of the first-order logic formula above; see if you can find a simple explanation.}
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
    
    \item Download the starter files for Problem Set Four from the website, then open the file $\mathsf{GraphTheory.cpp}$
    and implement a function
    \begin{center}
    \begin{minipage}{0.5\textwidth}
    \begin{minted}{cpp}
    bool isIndependentSet(Graph G, std::set<Node> I)
    \end{minted}
    \end{minipage}
    \end{center}
    that takes as input a graph $G$ and a set $I$, then returns whether $I$ is an independent set in $G$. The definition of the $\mathsf{Graph}$ type is provided in $\mathsf{GraphTheory.h}$. 
    
    Our provided starter code contains logic that, given a graph $G$, finds the largest independent set in $G$ by making a lot of repeated calls to $\mathsf{isIndependentSet}$. You might want to look over some of the sample graphs to get a feel for what large independent sets look like.
    
    \begin{shaded}
    Submit your edited $\mathsf{GraphTheory.cpp}$ file through Gradescope. 
    \end{shaded}

\end{enumerate}

You want to conduct a poll for an election and would like to survey people where no two people in the group know each other so that you can get a good representative sample of the population. Ideally, you'd find a large group of mutual strangers so that your poll has good statistical power and avoids \textit{sampling bias}, a weakness of a poll in which the sampled population isn't representative of the larger population.

\begin{enumerate}[resume*]
    \item 
    Explain how to model this problem as looking for a large independent set in a certain graph. What would the nodes in your graph be? What would the edges be? And why would an independent set have the properties you want? No formal proof is necessary, but do justify your answer.
    
    \annotate{You don't need to tell us how to actually \emph{find} that independent set. That's a question for another day...}
    
    \begin{shaded}
    Write your answer and justification here.
    \end{shaded}
\end{enumerate}

A \textbf{\textit{vertex cover}} in a graph $G = (V, E)$ is a set $C \subseteq V$ with the following property:
$$\forall x \in V.\ \forall y \in V.\ (\{x, y\} \in E \rightarrow x \in C \lor y \in C).$$
That's a bit of a mouthful, but this definition isn't as tough as it seems.

\begin{enumerate}[resume*]
    \item Translate the definition of a vertex cover into plain English, similarly to what you did in part (i).
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
    
    \item Implement a function
    \begin{center}
    \begin{minipage}{0.5\textwidth}
    \begin{minted}{cpp}
    bool isVertexCover(Graph G, std::set<Node> C)
    \end{minted}
    \end{minipage}
    \end{center}
    that takes as input a graph $G$ and a set $C$, then returns whether $C$ is a vertex cover of $G$. The definition of the $\mathsf{Graph}$ type is provided in $\mathsf{GraphTheory.h}$.
    
    
    Our provided starter code contains logic that, given a graph $G$, finds the smallest vertex cover in $G$ by making a lot of repeated calls to $\mathsf{isVertexCover}$. You might want to look over some of the sample graphs to get a feel for what small vertex covers look like.
    
    \begin{shaded}
    Submit your edited $\mathsf{GraphTheory.cpp}$ file through Gradescope. 
    \end{shaded}

\end{enumerate}

There's a close connection between independent sets and vertex covers.

\begin{enumerate}[resume*]
    \item Let $G = (V, E)$ be a graph and $C$ be a vertex cover of $G$. Prove that $V - C$ is an independent set of $G$.
    
    \annotate{Be sure to use the formal definitions of the relevant terms here. It's a lot easier to see what's going on here if you draw out some sample graphs, along with sample vertex covers and independent sets.}
    
    \begin{shaded}
    Provide a proof here. 
    \end{shaded}

\end{enumerate}

\pagebreak

\section{Symmetries, Permutations, and Automorphisms}

One of the more beautiful concepts in mathematics is \textit{symmetry}. Chances are that you have some intuitive conception of what ``symmetry'' means, and not just in the binary relation sense. For example, the letter M looks like itself when you look at it in a mirror, and the number 8 looks like itself if you flip it horizontally or rotate it $180^\circ$. \\

Now that we're studying graphs, we can ask what it means for a graph to be symmetric. For example, consider the graph of the \{5 / 2\} star shown below. This graph has many symmetries -- if you flip it horizontally, or rotate it $72^\circ$, the resulting graph looks identical. But this notion of ``looks identical'' appeals to our human visual system, which, as you've probably experienced, is easily tricked. Is there a way to come up with a more rigorous definition of ``symmetry?'' \\

Let's begin by labeling the nodes of this graph in whatever way we'd like. For convenience, we'll use the numbers 0, 1, 2, 3, and 4, following our star-drawing convention. Now, take the graph shown below and rotate it one fifth of a revolution clockwise, as shown here:

\begin{center}
\begin{minipage}{0.45\textwidth}
\begin{flushright}
\tikzset{every state/.style={inner sep=1pt,minimum size=0pt}}
\begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}]
  \node[state] (0) at (234:3) {0};
  \node[state] (1) at (162:3) {1};
  \node[state] (2) at (90:3) {2};
  \node[state] (3) at (18:3) {3};
  \node[state] (4) at (306:3) {4};
  \coordinate (a1) at (66:3);
  \coordinate (a2) at (138:3);
  \coordinate (a3) at (210:3);
  \coordinate (a4) at (282:3);
  \coordinate (a5) at (364:3);
  \coordinate (b1) at (42:3);
  \coordinate (b2) at (114:3);
  \coordinate (b3) at (186:3);
  \coordinate (b4) at (258:3);
  \coordinate (b5) at (340:3);
  \path[-] 
    (0) edge node {} (2)
    (2) edge node {} (4)
    (4) edge node {} (1)
    (1) edge node {} (3)
    (3) edge node {} (0);
  \path[->,blue,line width=1mm] 
    (a1) edge [bend left=30] node {} (b1)
    (a2) edge [bend left=30] node {} (b2)
    (a3) edge [bend left=30] node {} (b3)
    (a4) edge [bend left=30] node {} (b4)
    (a5) edge [bend left=30] node {} (b5);
\end{tikzpicture}
\end{flushright}
\end{minipage}
\hfill
\begin{minipage}{0.45\textwidth}
\tikzset{every state/.style={inner sep=1pt,minimum size=0pt}}
\begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}]
  \node[state] (0) at (162:3) {0};
  \node[state] (1) at (90:3) {1};
  \node[state] (2) at (18:3) {2};
  \node[state] (3) at (306:3) {3};
  \node[state] (4) at (234:3) {4};
  \path[-] 
    (0) edge node {} (2)
    (2) edge node {} (4)
    (4) edge node {} (1)
    (1) edge node {} (3)
    (3) edge node {} (0);
\end{tikzpicture}
\end{minipage}
\end{center}

If you'll notice, this operation on the graph corresponds to finding a permutation of the labels on the nodes. Specifically, the node 0 ended up where the node 1 used to be, the node 1 ended up where the node 2 used to be, etc. And hey! We have a way of describing transformations like that.

\begin{enumerate}[label=\roman*.]
    \item Describe the permutation that the above rotation corresponds to using two-line notation. No justification is necessary.
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
\end{enumerate}

Similarly, let's imagine that we mirror the graph horizontally, as shown here:

\begin{center}
\begin{minipage}{0.45\textwidth}
\begin{flushright}
\tikzset{every state/.style={inner sep=1pt,minimum size=0pt}}
\begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}]
  \node[state] (0) at (234:3) {0};
  \node[state] (1) at (162:3) {1};
  \node[state] (2) at (90:3) {2};
  \node[state] (3) at (18:3) {3};
  \node[state] (4) at (306:3) {4};
  \coordinate (a) at (90:3.5);
  \coordinate (b) at (270:3);
  \path[-] 
    (0) edge node {} (2)
    (2) edge node {} (4)
    (4) edge node {} (1)
    (1) edge node {} (3)
    (3) edge node {} (0);
  \path[-,thin,densely dotted]
    (a) edge node {} (b);
\end{tikzpicture}
\end{flushright}
\end{minipage}
\hfill
\begin{minipage}{0.45\textwidth}
\tikzset{every state/.style={inner sep=1pt,minimum size=0pt}}
\begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}]
  \node[state] (4) at (234:3) {4};
  \node[state] (3) at (162:3) {3};
  \node[state] (2) at (90:3) {2};
  \node[state] (1) at (18:3) {1};
  \node[state] (0) at (306:3) {0};
  \path[-] 
    (0) edge node {} (2)
    (2) edge node {} (4)
    (4) edge node {} (1)
    (1) edge node {} (3)
    (3) edge node {} (0);
\end{tikzpicture}
\end{minipage}
\end{center}

We can similarly think of this as a permutation. For example, node 1 maps to where node 3 used to be.

\begin{enumerate}[resume*]
    \item Describe the permutation that the above mirroring corresponds to using two-line notation. No justification is necessary.
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
\end{enumerate}

There are a number of other symmetries of this graph, and each one of them corresponds to a permutation of the nodes. However, not all node permutations correspond to symmetries. For example, imagine that we permute the nodes as shown here:

\begin{center}
\begin{minipage}{0.45\textwidth}
\begin{flushright}
\tikzset{every state/.style={inner sep=1pt,minimum size=0pt}}
\begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}]
  \node[state] (0) at (234:3) {0};
  \node[state] (1) at (162:3) {1};
  \node[state] (2) at (90:3) {2};
  \node[state] (3) at (18:3) {3};
  \node[state] (4) at (306:3) {4};
  \path[-] 
    (0) edge node {} (2)
    (2) edge node {} (4)
    (4) edge node {} (1)
    (1) edge node {} (3)
    (3) edge node {} (0);
\end{tikzpicture}
\end{flushright}
\end{minipage}
\hfill$\xRightarrow{\hphantom{-} ? \hphantom{-}}$\hfill
\begin{minipage}{0.45\textwidth}
\tikzset{every state/.style={inner sep=1pt,minimum size=0pt}}
\begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}]
  \node[state] (0) at (234:3) {0};
  \node[state] (3) at (162:3) {3};
  \node[state] (1) at (90:3) {1};
  \node[state] (4) at (18:3) {4};
  \node[state] (2) at (306:3) {2};
  \path[-] 
    (0) edge node {} (1)
    (1) edge node {} (2)
    (2) edge node {} (3)
    (3) edge node {} (4)
    (4) edge node {} (0);
\end{tikzpicture}
\end{minipage}
\end{center}

Notice that, in the original graph, nodes 0 and 2 were adjacent, but after permuting the nodes they're no longer adjacent to one another. (Remember that \textit{adjacent} means ``directly linked by an edge;'' contrast this with \textit{connected}, which has a different meaning.) Similarly, in the original graph, nodes 0 and 1 were \textit{not} adjacent, but after applying the permutation they now are.

At this point, we've seen some positive examples of cases where we \textit{can} use permutations to model symmetries, along with a negative example of where we \textit{can't} use permutations to model symmetries. The question is, what was special about those original permutations? It's that they have the following property: those permutations keep adjacent nodes adjacent and keep non-adjacent nodes non-adjacent.

Formally speaking, let $G = (V, E)$ be a graph. A permutation $\sigma$ of the nodes of $V$ is called an \emph{automorphism} if the following is true about $\sigma$:
$$\forall u \in V. \forall v \in V . (\{u, v\} \in E \iff \{\sigma(u), \sigma(v)\} \in E)$$

The mathematical term ``automorphism'' (``self shape'') might seem really scary here, but it's just a fancy way of pinning down what we've been describing with the term ``symmetry.'' Restating the above in plain English, a permutation is an \emph{automorphism} of $G$ if
\begin{itemize}
    \item any two nodes that are adjacent in $G$ stay adjacent after applying $\sigma$, and
    \item any two nodes that aren't adjacent in $G$ stay nonadjacent after applying $\sigma$.
\end{itemize}

The permutations that you described in parts (i) and (ii) are automorphisms, while the permutation shown above on this page isn't. The rest of this question explores properties of automorphisms.

\begin{enumerate}[resume*]
    \item How many automorphisms does the graph of \{5 / 2\} have? Briefly describe what they are. No formal proof is needed.
    
    \annotate{Use your intuition behind what automorphisms are designed to formalize.}
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
    
    \item Consider the graph shown below. It has two automorphisms. What are they? Express your answer using two-line notation.

    \begin{center}
    \begin{minipage}{0.5\textwidth}
    \tikzset{every state/.style={inner sep=1pt,minimum size=0pt}}
    \begin{tikzpicture}[node distance=2cm,on grid,auto,baseline={(current bounding box.north)}]
      \node[state] (1) {1};
      \node[state] (2) [right=of 1] {2};
      \node[state] (3) [right=of 2] {3};
      \node[state] (4) [right=of 3] {4};
      \path[-] 
        (1) edge node {} (2)
        (2) edge node {} (3)
        (3) edge node {} (4)
        (1) edge [bend left=50] node {} (3);
    \end{tikzpicture}
    \end{minipage}
    \end{center}
    
    A graph is just a pair of a set of nodes and a set of edges. We can draw a graph $G = (V, E)$ in two-dimensional space as a collection of circles and lines in lots of different ways. Sometimes, those drawings make it really easy to find symmetries. Sometimes, those drawings make it really hard to find symmetries.
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
    
\end{enumerate}

To round out our discussion of automorphisms, we'd like you to prove one nice, formal result about them.

\begin{enumerate}[resume*]
    \item Let $G = (V, E)$ be a graph and let $\sigma$ and $\tau$ be two automorphisms of $G$. Prove that $\tau \circ \sigma$ is also an automorphism of $G$.
    
    \annotate{Write out the definition of an automorphism and make a list of what you'll need to show.}
    
    \begin{shaded}
    Provide a proof here.
    \end{shaded}
\end{enumerate}

\pagebreak

\section{Bipartite Graphs}

There are a few famous families of graphs that come up over and over again. One of the most important types of graphs in computer science is the \textit{bipartite graph}, which is the focus of this problem. \\

Let's begin with a formal definition of bipartite graphs. An undirected graph $G = (V, E)$ is called \emph{bipartite} if there exists two sets $V_1$ and $V_2$ such that
\begin{itemize}
\item every node $v \in V$ belongs to exactly one of $V_1$ and $V_2$,
and
\item every edge $e \in E$ has one endpoint in $V_1$ and the other in $V_2$.
\end{itemize}

The sets $V_1$ and $V_2$ here are called the \textit{\textbf{bipartite classes}} of $G$. To help you get a better sense for why bipartite graphs are important and where they show up, let's work through a couple of examples. 

\begin{enumerate}[label=\roman*]
    \item Consider a graph where each node represents a square on a chessboard and where there's an edge between any pair of squares that are immediately adjacent in one of the four cardinal directions (up, down, left, and right). Explain why this is a bipartite graph by telling us what the bipartite classes are and briefly explaining why all the edges have one endpoint in each bipartite class.

    \annotate{Draw lots of pictures!}
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
    
    \item Consider a graph where each node represents a person at a company and there's an edge between any person and their boss. (Since edges are undirected, that also means that there's an edge from each person to all the people who report to them). You can assume everyone has a single boss, except for people who are in charge of a company, who have no bosses at all. Explain why this is a bipartite graph, along the lines of what you did in part (i).
    
    \annotate{Draw lots of pictures!}
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
\end{enumerate}

Bipartite graphs have many interesting properties. One of the most fundamental is this one:
\begin{center}
\emph{Theorem:} An undirected graph is bipartite if and only if it contains no cycles of odd length.
\end{center}

The forward direction of this implication has a nice intuition.

\begin{enumerate}[resume*]
    \item Explain, intuitively, why if $G$ is bipartite, then it has no cycles of odd length. Specifically, give us a brief, informal explanation as to why every cycle in $G$ has to have even length.
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
\end{enumerate}

The reverse direction of this implication -- that if $G$ has no cycles of odd length, then $G$ is bipartite -- requires a different sort of argument. \\

Let's pick some arbitrary graph $G = (V, E)$ that has no cycles of odd length. For simplicity's sake, we'll assume that $G$ has just one connected component. If $G$ has two or more connected components, we can essentially treat each one of them as independent graphs. \textit{(Do you see why?)} \\

Now, choose any node $v \in V$. Using node $v$ as an ``anchor point,'' we can define two sets $V_1$ and $V_2$ that we'll need for the remainder of this argument:
\begin{gather*}
V_1 = \{ x \in V \mid \text{there is an odd-length path from $v$ to $x$} \} \\
V_2 = \{ x \in V \mid \text{there is an even-length path from $v$ to $x$} \}
\end{gather*}
This turns out to be a really useful way to group the nodes of $G$.

\begin{enumerate}[resume*]
\item Given the choices of $G$ and $v$ from above, prove that $V_1$ and $V_2$ have no nodes in common.

\annotate{Remember that there might be multiple different paths of 
different lengths from v to some other node x, so
be careful not to talk about ``the'' path between v and x. Also note that these \emph{do not} have to be \emph{simple} paths.}

\begin{shaded}
Provide a proof here.
\end{shaded}

\item Using your result from part (iv), prove that $G$ is bipartite.

\annotate{The most common mistake on this problem is to not address all the parts of the definition of a bipartite graph. So start off by writing down a list of what you need to prove, then address each part in turn.}

\begin{shaded}
Provide a proof here.
\end{shaded}

\end{enumerate}

\pagebreak

On this problem set, we've included four optional fun problems you can play around with. You're welcome to play around with any number of them, but \emph{please submit answers to at most one of these problems} with your problem set. We, unfortunately, don't have TA bandwidth to grade all of them. If you submit solutions to more than one of them, we'll choose one to grade arbitrarily.

\section*{Optional Fun Problem 1: Hugs All Around! (Extra Credit)}

There's a party with 137 attendees. Each person is either \emph{honest}, meaning that they \textit{always} tell the truth,
or \emph{mischievous}, meaning that they \textit{never} tell the truth. After everything winds down, everyone is asked how many \underline{\emph{honest}} people they hugged at the party.
Surprisingly, each of the numbers 0, 1, 2, 3, \dots, and 136 was given as an answer exactly once. \\

How many honest people were at the party?
Prove that your answer is correct and that no other answer
could be correct.
\begin{shaded}
Write your answer and proof here.
\end{shaded}

\section*{Optional Fun Problem 2: How Many Functions Are There? (Extra Credit)}
If $A$ and $B$ are sets, we can define the set $B^A$
to be the set of all functions from $A$ to $B$. Formally speaking:
\begin{equation*}
B^A = \{ f\ |\ f : A \rightarrow B \}
\end{equation*}
Prove that $|\N| < |\N^{\N}|$. This shows
that $\aleph_0 < \aleph_0^{\aleph_0}$. Isn't infinity weird?

\begin{shaded}
Provide a proof here.
\end{shaded}

\section*{Optional Fun Problem Three: Chemical Automorphisms}

Below is a graph of the molecular structure of octomethylcyclotetrasiloxane. How many automorphisms does this graph have? Justify your answer, but no formal proof is required.

% This image takes a very long time to compile, so we've commented it out. Feel free to uncomment
% it if you like.

% \begin{center}
% \begin{minipage}
% \begin{tikzpicture}[every node/.style={circle,draw=black,minimum size=7pt,fill=white}]
% \draw (0:3) node (root1) {} -- (45:3) node (1) {} -- (90:3) node (root2) {} -- (135:3) node (2) {} -- (180:3) node (root3) {} -- (225:3) node (3) {} -- (270:3) node (root4) {} -- (315:3) node (4) {} -- (root1)
% \draw (root1) -- ++ (330:1) node (subtree11) {}
% \draw (subtree11) -- ++ (290:0.8) node (leaf111) {}
% \draw (subtree11) -- ++ (330:0.8) node (leaf112) {}
% \draw (subtree11) -- ++ (40:0.8) node (leaf113) {}
% \draw (root1) -- ++ (30:1) node (subtree12) {}
% \draw (subtree12) -- ++ (350:0.8) node (leaf121) {}
% \draw (subtree12) -- ++ (30:0.8) node (leaf122) {}
% \draw (subtree12) -- ++ (70:0.8) node (leaf123) {}
% \draw (root2) -- ++ (60:1) node (subtree21) {}
% \draw (subtree21) -- ++ (20:0.8) node (leaf211) {}
% \draw (subtree21) -- ++ (60:0.8) node (leaf212) {}
% \draw (subtree21) -- ++ (100:0.8) node (leaf213) {}
% \draw (root2) -- ++ (120:1) node (subtree22) {}
% \draw (subtree22) -- ++ (80:0.8) node (leaf221) {}
% \draw (subtree22) -- ++ (120:0.8) node (leaf222) {}
% \draw (subtree22) -- ++ (160:0.8) node (leaf223) {}
% \draw (root3) -- ++ (150:1) node (subtree31) {}
% \draw (subtree31) -- ++ (110:0.8) node (leaf311) {}
% \draw (subtree31) -- ++ (150:0.8) node (leaf312) {}
% \draw (subtree31) -- ++ (190:0.8) node (leaf313) {}
% \draw (root3) -- ++ (210:1) node (subtree32) {}
% \draw (subtree32) -- ++ (170:0.8) node (leaf321) {}
% \draw (subtree32) -- ++ (210:0.8) node (leaf322) {}
% \draw (subtree32) -- ++ (250:0.8) node (leaf323) {}
% \draw (root4) -- ++ (240:1) node (subtree41) {}
% \draw (subtree41) -- ++ (200:0.8) node (leaf411) {}
% \draw (subtree41) -- ++ (240:0.8) node (leaf412) {}
% \draw (subtree41) -- ++ (280:0.8) node (leaf413) {}
% \draw (root4) -- ++ (300:1) node (subtree42) {}
% \draw (subtree42) -- ++ (260:0.8) node (leaf421) {}
% \draw (subtree42) -- ++ (300:0.8) node (leaf422) {}
% \draw (subtree42) -- ++ (340:0.8) node (leaf423) {};
% \end{tikzpicture}
% \end{minipage}
% \end{center}

\begin{shaded}
Write your answer and justification here.
\end{shaded}


\section*{Optional Fun Problem 4: Chromatic and Independence Numbers}
Recall that if $G$ is a graph, then $\chi(G)$ represents the \emph{chromatic number} of $G$, the minimum number of colors needed to paint each node of $G$ so no two adjacent nodes of $G$ are the same color. The \emph{independence number} of a graph, denoted $\alpha(G)$, is the size of the largest independent set in $G$. \\

Let $n$ be an arbitrary positive natural number. Prove that if $G$ is an undirected graph with exactly $n^2+1$ nodes, then $\chi(G) \geq n+1$ or $\alpha(G) \geq n+1$ (or both). \\

\annotate{You should definitely check out what the Guide to Proofs on Discrete Structures' advice for proving $P \lor Q$.}

\begin{shaded}
Provide a proof here.
\end{shaded}


\end{document}