%
% 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.
%
\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{Sachin Padmanabhan}
\date{\today}
\lhead{Sachin Padmanabhan}
\chead{Problem Set \#4}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Winter 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}}
\begin{document}
\maketitle
\section{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.
\textit{\textcolor{blue}{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}
\begin{answer}
Write your answer here.
\end{answer}
\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{center}
$f(n, x) = $ \underline{\hspace{35ex}}
\end{center}
where $n \in \N$ and $x \in \{\bigstar, \smiley{}\}$.
\textit{\textcolor{blue}{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.}}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\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?
\section{Understanding Diagonalization}
Proofs by diagonalization are tricky and rely on nuanced arguments.
In this problem, we'll ask you to review
the diagonalization proof we covered in the Guide to 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$?
\textit{\textcolor{blue}{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}
\begin{answer}
Write your answer here.
\end{answer}
\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}
\begin{answer}
Write your answer here.
\end{answer}
Provide 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}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Repeat part (ii) of this problem using the function $f$ from part (iii).
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\end{enumerate}
\section{Simplifying Cantor's Theorem?}
In our proof of Cantor's theorem,
we proved that $|S| \neq |\wp(S)|$ by using a diagonal argument.
Below is a purported proof that $|S| \neq |\wp(S)|$
that doesn't use a diagonal argument:
\vspace{-1em}
\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?
by pointing to a specific claim that's made here that's incorrect and explaining why it's incorrect.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\section{Paradoxical Sets}
What happens if we take \textit{absolutely everything} and throw it into a set?
If we do, we would get a set called the \textbf{\textit{universal set}},
which we denote $\mathscr{U}$:
$$\mathscr{U} = \{ x \mid \text{$x$ exists} \}$$
Absolutely everything would belong to this set:
\begin{center}
$1 \in \mathscr{U}$ \quad $\N \in \mathscr{U}$ \quad $\text{CS103} \in \mathscr{U}$ \quad $\text{whimsy} \in \mathscr{U}$
\end{center}
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|$.
\textit{\textcolor{blue}{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 \textit{\textbf{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|$.
\textit{\textcolor{blue}{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.}}
\begin{shaded}
Provide a proof here.
\end{shaded}
\item Using your result from parts (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.
When this was discovered at the start of the twentieth century,
it caused quite a lot of chaos in the math 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).
\section{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.
\textit{\textcolor{blue}{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 of
what independent sets are.}}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\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}
$\mathsf{bool\ isIndependentSet(Graph\ G,\ std::set I)}$
\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}
\item 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.
Explain how you might model this problem in terms of building some sort of graph, then finding a
large independent set in it. Briefly justify your answer; no formal proof is necessary.
\textit{\textcolor{blue}{We don't
want you to design an algorithm for finding large independent sets. Instead, imagine you have a
program that you give as input a graph and that hands back to you an independent set in that graph. What
graph would you give that program as input? What would you do with the output?}}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\end{enumerate}
The size of an independent set is the number of nodes in it.
Formally speaking, if $I$ is an independent set,
then the size of $I$ is given by $|I|$. The \textit{\textbf{independence number}} of a graph $G$, denoted $\mathbf{\alpha(G)}$, is the size of the largest independent set in $G$. (Note that there can be many different independent sets in a graph $G$ that are
all tied for the largest.)
\begin{enumerate}[resume*]
\item Edit the file $\mathsf{PartA.graph}$ in the $\mathsf{res/}$ directory to define a graph $G$ where $G$ has exactly five
nodes and $\alpha(G) = 5$.
\begin{shaded}
Submit your edited $\mathsf{PartA.graph}$ file through Gradescope.
\end{shaded}
\item Edit the file $\mathsf{PartB.graph}$ in the $\mathsf{res/}$ directory to define a graph $G$ where $G$ has exactly five
nodes and $\alpha(G) = 1$.
\begin{shaded}
Submit your edited $\mathsf{PartB.graph}$ file through Gradescope.
\end{shaded}
\end{enumerate}
A graph can contain multiple different independent sets.
\begin{enumerate}[resume*]
\item Prove or disprove: if $G = (V, E)$ is a graph and $I_1$ and $I_2$ are independent sets in $G$, then $I_1 \cap I_2$ is
an independent set in $G$.
\textit{\textcolor{blue}{Independent sets are specified using a definition given in first-order logic. Make sure your proof is structured
around that definition, the same way that proofs of reflexivity, symmetry, etc. are structured around
those first-order definitions.}}
\begin{shaded}
Provide a proof or disproof here.
\end{shaded}
\end{enumerate}
\section{Vertex Covers}
A \textbf{\textit{vertex cover}} in a graph $G = (V, E)$ is a set
$C \subseteq V$ with the following property:
$$\forall u \in V.\ \forall v \in V.\ (\{u, v\} \in E
\rightarrow u \in C \lor v \in C).$$
This question explores vertex covers and their properties.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Translate the definition of a vertex cover into plain English.
No justification is necessary.
\textit{\textcolor{blue}{As before, you may want to draw pictures. See if you can find an explanation that's more than just a literal
translation of the above statement.}}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Implement a function
\begin{center}
$\mathsf{bool\ isVertexCover(Graph\ G,\ std::set C)}$
\end{center}
that takes as input a graph $G$ and a set $C$, then returns whether $C$ is a vertex cover of $G$.
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 vertex covers look like.
\begin{shaded}
Submit your edited $\mathsf{GraphTheory.cpp}$ file through Gradescope.
\end{shaded}
\item Suppose that you have a map of a city's roads and streets (assume that the roads are set up so that
it's possible to walk between any two points in the city). You want to set up information kiosks so
that no matter where you are, you never need to walk more than a block to get to a kiosk. You
also want to use as few information kiosks as possible to accomplish this. Explain how you might
model this problem by building some sort of graph and looking for a small vertex cover in that
graph. Briefly justify your answer; no formal proof is necessary.
\textit{\textcolor{blue}{Along the lines of part (iii) of the previous problem, assume you have a black box for finding small vertex
covers and don't try to come up with an algorithm on your own. What graph would you hand into that
black box? What would you do with the resulting vertex cover it hands back to you?}}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\end{enumerate}
The size of a vertex cover is the number of nodes in it.
Formally speaking, if $C$ is a vertex cover,
then the size of $C$ is given by $|C|$. The \textbf{\textit{vertex cover number}} of a graph $G$, denoted $\mathbf{\tau(G)}$, is the size of the smallest vertex cover of $G$. (Note that there can be many different vertex covers in a graph $G$ that are all tied for
the smallest.)
\begin{enumerate}[resume*]
\item Edit the file $\mathsf{PartC.graph}$ in the $\mathsf{res/}$ directory to define a graph $G$ where $G$ has exactly five
nodes and $\tau(G) = 0$.
\begin{shaded}
Submit your edited $\mathsf{PartC.graph}$ file through Gradescope.
\end{shaded}
\item Edit the file $\mathsf{PartD.graph}$ in the $\mathsf{res/}$ directory to define a graph $G$ where $G$ has exactly five
nodes and $\tau(G) = 4$.
\begin{shaded}
Submit your edited $\mathsf{PartD.graph}$ file through Gradescope.
\end{shaded}
\end{enumerate}
As with independent sets, graphs can contain multiple different vertex covers.
\begin{enumerate}[resume*]
\item Prove or disprove: if $G = (V, E)$ is a graph and $C_1$ and $C_2$ are vertex covers of $G$, then $C_1 \cap C_2$ is
a vertex cover of $G$.
\begin{shaded}
Provide a proof or disproof here.
\end{shaded}
\end{enumerate}
Vertex covers have some really cool applications. Check out \href{https://www.youtube.com/watch?v=ZCVAGb1ee8A&feature=youtu.be}{\underline{this Numberphile video}} for one of them!
\section{Chromatic and Clique Numbers}
Recall from lecture that a \textit{\textbf{k-vertex coloring}} of a graph is a way of coloring each node in the graph one of
\underline{up to} $k$ different colors such that no two adjacent nodes are the same color. The \textit{\textbf{chromatic number}} of a graph, denoted $\mathbf{\chi(G)}$, is the minimum value of $k$ for which a $k$-vertex coloring exists.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Implement a function
\begin{center}
$\mathsf{bool\ isKVertexColoring(Graph\ G,
std::map\ colors,
std::size\_t\ k);}$
\end{center}
that takes as input a graph, a mapping from nodes in the graph to colors, and a number $k$, then returns
whether the indicated coloring is a $k$-vertex coloring. You can assume that the map has one
key for each node in the graph and that the only keys in the map are nodes in $G$. (The type
$\mathsf{std::size\_t}$ represents a natural number.)
Our provided starter code contains some logic that, given a graph $G$, finds a minimum $k$-vertex coloring
of $G$ by making a lot of calls to your $\mathsf{isKVertexColoring}$ function. We recommend taking
some time to look at a few sample graphs and their minimum colorings -- they're quite pretty!
\begin{shaded}
Submit your edited $\mathsf{GraphTheory.cpp}$ file through Gradescope.
\end{shaded}
\end{enumerate}
Here's a new definition. A \textit{\textbf{clique}} in a graph $G = (V, E)$ is a set $K \subseteq V$ with the following property:
\begin{equation*}
\forall u \in K.\ \forall v \in K.\ (u \ne v \rightarrow \{u, v\} \in E)
\end{equation*}
This question explores the connection between cliques and chromatic numbers.
\begin{enumerate}[resume*]
\item Translate the definition of a clique into plain English. No justification is necessary.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Implement a function
\begin{center}
$\mathsf{bool\ isClique(Graph\ G, std::set\ K)}$
\end{center}
that takes as input a graph $G$ and a set $K$, then returns whether $K$ is a clique in $G$.
Our provided starter code contains some logic that, given a graph $G$, finds the largest clique
in $G$ by making a lot of calls to your $\mathsf{isClique}$ function. You may want to take a look at some of the
provided sample graphs to see what large cliques look like.
\begin{shaded}
Submit your edited $\mathsf{GraphTheory.cpp}$ file through Gradescope.
\end{shaded}
\end{enumerate}
\textit{\textbf{(We will cover the material necessary to solve the remainder of this problem in Monday's lecture.)}} \\
The size of a clique $K$, denoted $|K|$, is the number of nodes in $K$. The \textbf{\textit{clique number}} of a graph, denoted
$\mathbf{\omega(G)}$, is the size of the largest clique in $G$.
\begin{enumerate}[resume*]
\item Prove that if $G$ is a graph, then $\chi(G) \ge \omega(G)$.
\textit{\textcolor{blue}{We're expecting you to write a formal proof here. It may be easiest to do this by contradiction.}}
\begin{shaded}
Provide a proof here.
\end{shaded}
\item Edit the file $\mathsf{PartE.graph}$ in the $\mathsf{res/}$ directory to contain a graph $G$ where $\chi(G) \ne \omega(G)$. This shows that, in general, the chromatic and clique numbers of a graph don't have to equal one another.
\textit{\textcolor{blue}{Aim to find the smallest example that you can. Although you aren't required to submit the simplest example
possible and we aren't asking for an explanation as to why your answer is correct, you should not feel satisfied
with your answer unless you can justify why it's got to be the simplest answer possible.}}
\begin{shaded}
Submit your edited $\mathsf{PartE.graph}$ file through Gradescope.
\end{shaded}
\end{enumerate}
\section{Chromatic and Independence Numbers}
\textit{\textbf{(We will cover the material necessary to solve this problem in Monday's lecture.)}} \\
In Problem Seven, you explored the connection between clique numbers and chromatic numbers. This
problem explores the connection between independence numbers and chromatic numbers. \\
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). \\
\textit{\textcolor{blue}{You should definitely check out what the Guide to Proofs on Discrete Structures says to do if you want to
prove a statement of the form $P \lor Q$ since it'll make this proof a lot easier to write!}}
\begin{shaded}
Provide a proof here.
\end{shaded}
\section{Bipartite Graphs}
An undirected graph $G = (V, E)$ is called \textbf{\textit{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 intuition for bipartite graphs,
suppose that you have a group of people and a list of restaurants.
You can illustrate which people like which restaurants by constructing
a bipartite graph where $V_1$ is the set of people,
$V_2$ is the set of restaurants,
and there's an edge
from a person $p$ to a restaurant $r$ if person $p$ likes restaurant $r$. \\
Bipartite graphs have many interesting properties.
One of the most fundamental is this one:
\begin{center}
\textit{An undirected graph is bipartite if and only if it contains no cycles
of odd length.}
\end{center}
Intuitively, a bipartite graph contains no odd-length cycles
because cycles alternate between the two groups $V_1$ and $V_2$,
so any cycle has to have even length. The trickier step is proving that if $G$ is a graph
that contains no cycles of odd length, then $G$ has to be bipartite. For now, assume
that $G$ has just one connected component; if $G$ has multiple connected components,
we can treat each one as a separate graph for the purposes of determining whether $G$ is bipartite.
(You don't need to prove this, but I'd recommend taking a minute to check why this is the case.) \\
Suppose $G$ is a connected,
undirected graph with no cycles of odd length.
Choose any node $v \in V$.
Let $V_1$
be the set of all nodes that are connected to $v$
by a path of odd length and $V_2$
be the set of all nodes connected
to $v$ by a path of even length.
(Note that these paths do not have to be simple paths).
Formally:
\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*}
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Prove that $V_1$ and $V_2$ have no nodes in common.
\textit{\textcolor{blue}{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 don't have to be simple paths.}}
\begin{shaded}
Provide a proof here.
\end{shaded}
\item Using your result from part (i),
prove that $G$ is bipartite.
\textit{\textcolor{blue}{What do you need to show to prove that every node belongs to one of exactly two sets? Make sure you can
point out how you are using the fact that G is connected and the fact that G has no cycles of odd length.}}
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
\section*{Optional Fun Problem 1:
Hugs All Around! (1 Point Extra Credit)}
There's a party with $137$ attendees.
Each person is either \textbf{\textit{honest}},
meaning that they \textit{always} tell the truth,
or \textbf{\textit{mischievous}},
meaning that they \textit{never} tell the truth. After everything winds down,
everyone is asked how many \underline{\textbf{\textit{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}
\begin{answer}
Write your answer here.
\end{answer}
Provide a proof here.
\end{shaded}
\section*{Optional Fun Problem 2:
How Many Functions Are There? (1 Point 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*}
Using the formal definition of the less-than relation over cardinalities, 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}
\end{document}