\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\def\zero{\multicolumn{1}{>{\columncolor{white}}c}{0}}
\def\colCell#1#2{\multicolumn{1}{>{\columncolor{#1}}c}{#2}}

\input{preamble.tex}

\begin{document}
\homework{15: Random Graphs}{Due Friday, Week 10}


Do \textbf{three} of the six problems listed here!  Have fun, prove all of your claims, and let me know if you have any questions!  

\begin{enumerate}

\item More Sim variations!  Consider the following game, which we can think of as \textbf{impartial} or \textbf{colorblind} Sim:
\begin{itemize}
\item There are two players, Player 1 and Player 2.  Their gameboard consists of $n$ points drawn on a plane.  Players alternate turns, and Player 1 starts first. 
\item On a given player's turn, they must connect two points that do not have a line drawn between them yet.  All lines are drawn in black.
\item You lose if your chosen move on any turn creates a triangle.
\end{itemize}

This is like Sim if you were colorblind (and thus to be safe had to avoid all triangles.)

Who wins\footnote{Warning: in general, this problem is open for general values of $n$ as far as I know.  See \href{http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.8.1904&rep=rep1&type=pdf}{``One-color Triangle Avoidance Games''} and \href{http://link.springer.com/article/10.1007/BF01271710}{``On Hajnal's Triangle-free Game''} for more information.    So a general solution for all $n$ is probably very hard, though if you can find it that would be really exciting!}   this game on $n=5$?  



\item Yet more Sim variations!  Consider the following game, which we can think of as \textbf{mis\`ere} \textbf{impartial} or \textbf{colorblind} Sim:
\begin{itemize}
\item There are two players, Player 1 and Player 2.  Their gameboard consists of $n$ points drawn on a plane.  Players alternate turns, and Player 1 starts first. 
\item On a given player's turn, they must connect two points that do not have a line drawn between them yet.  All lines are drawn in black.
\item You \textbf{win} if your chosen move on any turn creates a triangle.
\end{itemize}

This is like mis\`ere Sim if you were colorblind.

Determine who wins this game for \textbf{all} values of $n$!  

\item Let $\mathcal{F}(\mathbb{N})$ denote the collection of all finite subsets of $\mathbb{N}$.  Prove that $\mathcal{F}(\mathbb{N}) \times \mathcal{F}(\mathbb{N})$ is a countable set.

\item Let $\langle \Omega, Pr\rangle$ be some probability space, and $A_1, A_2 \ldots A_k$  a collection of mutually independent events in this space. 
\begin{enumerate}
\item Prove that $\displaystyle Pr(A_1 \cap A_2 \cap \ldots \cap A_k) = \prod_{i=1}^k Pr(A_i)$.
\item For any event $A_i$, let $A_i^c = \{\omega \in \Omega ~|~ \omega \notin A_i\}$; i.e. $A_i^c$ is the \textbf{complement} to $A_i$.  Prove that the events $A_1^c, \ldots A_k^c$ are all mutually independent.
\end{enumerate}

\item Take the Rado graph $R$  from Wednesday, week 9's lecture.  Delete finitely many vertices and edges from this graph, to get some new graph $R'$.  Is $R'$ isomorphic to $R$?  If it is, prove your claim; if it is not, give an example that proves that this can fail.

\item Consider the graph $\mathcal{B}$ on the vertex set $\mathbb{N}$, formed by drawing an edge $\{x,y\}$ between two numbers $x, y$ whenever either the $x$-th bit of $y$'s binary representation is 1, or the $y$-th bit of $x$'s binary representation is 1.   So, for example:
\begin{itemize}
\item The two vertices $46, 3$ would be connected, as $46 = 101110_{\textrm{binary}}$, and the third bit of this sequence is a 1.  
\item Similarly, the two vertices $19, 4$ would not be connected; $19 = 10011_{\textrm{binary}}$, the fourth bit of which is 0, and similarly $4 = 100_{\textrm{binary}}$, and the 19th bit\footnote{By the ``19th bit of $100_{\textrm{binary}}$, we just mean the 19th bit of this number in binary, where we can naturally think of $100_{\textrm{binary}} = 000\ldots 0 100_{\textrm{binary}}$.  In other words, adding leading zeroes doesn't change numbers, and lets us refer to the ``$n$-th bit'' of any number and always have that quantity be defined.} of that sequence is also 0. 
\end{itemize}


Show that this graph is isomorphic to the Rado graph.


\end{enumerate}



\end{document}