\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{14: The Return of Set 12}{Due Friday, Week 9}



Three things with this set:
\begin{itemize}
\item Because it came out late, I'm considering it as both Friday and Monday's problem set!  So there is no set that will come out Monday / you just have 3 problems to do this week.
\item Many of the problems here may seem familiar; this is because several of them are variations on problems from set 12, with additional hints to make them more approachable!
\item You cannot use results from set 12 on this set.  If you successfully solved a problem on set 12 that has reoccurred on this set, then you should probably try a different problem.  (If you tried a problem but it didn't work, feel free to retry that problem!)
\end{itemize}
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 If you did problems 2 or 3 on set 12, you are probably tired of Sim.  Accordingly, if someone were to challenge you to a game of Sim, you might want to instead \textbf{lose} as quickly as possible, just to get the game over with!  

As mathematicians, we can turn this into another game: \textbf{Miser\'e Sim}.
\begin{itemize}
\item There are two players, Red and Blue.  Their gameboard consists of $n$ points drawn on a plane.  Players alternate turns, and Red starts first. 
\item On a given player's turn, they must connect two points that do not have a line drawn between them yet, with a line of their given color.
\item The game ends when a monochromatic triangle is drawn on the board, in which case that player \textbf{wins}, because they have ended the game!
\end{itemize}
Show that the first player can force a ``win'' in this game whenever $n \geq 5$.  

\item Take $K_{10}$, and color each of its edges red or blue.  Prove that there are either two disjoint\footnote{As before, two graphs $G, H$ are disjoint if and only if they share no vertices or edges in common.} red triangles or two disjoint blue triangles.  

Hints:\ there are many ways to approach this problem.  One way that I took was the following:
\begin{itemize}
\item Mimicking the first problem on set 12, show that there are at least 20 monochrome triangles in our two-colored graph.
\item Show that if all of the monochrome triangles are the same color (i.e.\ there are none of the other color,) then our claim holds.
\item Otherwise, by symmetry (because the names of the colors don't matter) there must be at least one red and one blue triangle.   Show that you can specifically find a red and a blue triangle with a vertex in common.  Call the union of those two triangles $G$.
\item Look at the five vertices that are not members of $G$; call the graph on those five vertices $H$.  If there is either a red or blue triangle among those five vertices, then our proof is done.  If there is not, what can you say about $H$?
\item Finally, use the structure you have established for $G, H$ to prove by contradiction that there must be two disjoing monochrome triangles of the same color.
\end{itemize}

\item Show that for any red-blue two-coloring of $K_{5n}$'s edges, there are at least $n$ disjoint red triangles or $n$ disjoint blue triangles, 

Hint: use induction, with problem 2 as your base case.  

\item For any $n$, find a red-blue two-coloring of $K_{5n-1}$ such that it is impossible to find $n$ disjoint red triangles or $n$ disjoint blue triangles.  

\item Define a \href{http://en.wikipedia.org/wiki/Hypergraph}{\textbf{$k$-hypergraph}} $G_k = (V,E)$ as follows:
\begin{itemize}
\item Vertices: some set $V$.
\item Edges, or ``hyperedges:'' a collection of subsets of $V$ of size $k$.
\end{itemize}
A graph, in this sense, is just a 2-hypergraph.  Hypergraphs are just the idea behind a graph, where we let edges be subsets of size $k$ instead of 2.

The complete $k$-hypergraph on $n$ vertices, $K_{n}^{(k)}$, is just a graph on the vertices $\{1,2,\ldots n\}$ along with all of the subsets of $\{1,2,\ldots n\}$ of size $k$.  A red-blue two-coloring of such a hypergraph is any way to assign each hyperedge one of the two colors red or blue.  Such a two-coloring is called monochrome if all of the edges are the same color.

Define the \textbf{hypergraph Ramsey number} $R(a,b; k)$ as the smallest value of $n$ such that any red-blue coloring of $K_{n}^{(k)}$ has either a red $K_{a}^{(k)}$ or a blue $K_b^{(k)}$.  Prove that $R(a,b; k)$ exists\footnote{You can use this result to prove the theorem from problem 6 last week, as we discussed then!} for any $a,b,k$. 


Hint: prove that 
\begin{align*}
R(a,b; k) \leq 1 + R\bigg( R(a, b-1; k), R(a-1, b; k); k-1\bigg).
\end{align*}



\item Given a graph $G$, a \textbf{dominating set} is any subset $S$ of $G$'s vertices such that every vertex not in $S$ has a neighbor in $S$.  

Suppose that $G$ is a $n$-vertex graph in which every vertex has degree at least $k$, for some value $k$.  Prove that $G$ has a dominating set of size at least $\displaystyle n\frac{1+ln(k+1)}{k+1}$.

Hint:\ Pick out a random subset $S$ of $G$'s vertices by flipping a coin for each vertex, and putting it in $S$ if and only if the coin comes up heads.  Suppose that your coin comes up heads with probability $p$, and tails with probability $1-p$.  

Let $T$ be the collection of all vertices that are not in $S$ that have no neighbors in $S$.  $S \cup T$ is a dominating set.  Can you find an upper bound on the expected value of $|S \cup T|$?




\end{enumerate}



\end{document}