\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{url}
\usepackage{amsmath}

% This is a file of macros and definitions that may come up in
% ANY LATEX paper.  Typically I'll use this file and some other file in the
% directory of the paper, this one for general math things, that one for
% things specific to that paper.
%
% font's used and general paper things.
\font\tenrm=cmr10
\font\ninerm=cmr9
\font\eightrm=cmr8
\font\sevenrm=cmr7
% \font\title=cmbx10 scaled \magstep1 % extra big title font
\font\ss=cmss10 % used by \proof
\font\smallcaps=cmcsc10 % used to label Theorems, etc.
% imhibit black bars on overflows
%
\overfullrule=0pt
%
% today's date
%
%
% English words that I always italizice in papers.
% Some words that appear in math mode alot that I wasn roman
%

\newcommand{\AREA}{{\rm AREA}}
\newcommand{\ALG}{{\rm ALG}}
\newcommand{\ACK}{{\rm ACK}}
\newcommand{\VC}{{\rm VC}}
\newcommand{\AC}{{\rm AC}}
\newcommand{\ZL}{{\rm ZL}}
\newcommand{\WOP}{{\rm WOP}}
\newcommand{\tree}{{\rm tree}}
\newcommand{\SUBSEQ}{{\rm SUBSEQ}}
\newcommand{\minor}{{\preceq_m}}
\newcommand{\minorp}{{\preceq_m'}}
\newcommand{\cminor}{{\preceq_{\rm c\hbox{-}m}}}
\newcommand{\GM}{{\rm  GM}}
\newcommand{\TREE}{{\rm  TREE}}
\newcommand{\R}{\rm  R} 
\newcommand{\B}{\rm  B} 
\newcommand{\G}{\rm  G} 
\newcommand{\Y}{\rm  P} 

\newcommand{\IO}{\exists^\infty}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}

\newcommand{\into}{{\rightarrow}}
\newcommand{\D}{{\sf D}}
\newcommand{\N}{{\sf N}}
\newcommand{\Z}{{\sf Z}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\reals}{{\sf R}}
\newcommand{\qd}{{\rm qd}}
\newcommand{\GE}[1]{{\equiv^{G}_{#1}}}
\newcommand{\TE}[1]{{\equiv^{T}_{#1}}}
\newcommand{\TES}[1]{{\equiv^{T}_{#1,{\rm S}}}}
\newcommand{\TEB}[1]{{\equiv^{T}_{#1,{\rm BOOL(S)}}}}
\newcommand{\LL}{{\cal{L}}}
\newcommand{\onepe}{1+\epsilon}
\newcommand{\oneme}{1-\epsilon}
\newcommand{\cool}{cool}
\newcommand{\nze}{numzeros}
\newcommand{\non}{numones}
\newcommand{\LR}[2]{ {\rm LR}_{{#2}}({#1})}
\newcommand{\LH}[2]{ {\rm LH}({#1};{#2})}
\newcommand{\bbb}{{\gamma}}
\newcommand{\COL}{{\rm COL}}
\newcommand{\card}[1]{\#(#1)}
\newcommand{\st}{\mathrel{:}}
\newcommand{\fhat}{{\hat{f}}}
\newcommand{\Ahat}{{\hat{A}}}

\begin{document}

\centerline{\bf Homework 11, Morally Due 12:30PM, Tue Apr 28  2026}


\begin{enumerate}

\item
(0 points) What is your name? 


\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(35 points) 

\begin{enumerate}
\item
(10 points)
Show that $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$
with a combinatorial proof. That is, show that the Right Hand Side
solves the problem {\it how many ways can I pick $k$ Ramsey Theorists from 
a set of $n$ Ramsey Theorists}. 

(You will use this in the next part.)

\item
(15 points) 
Show that, for all $a,b\ge 2$,

$R(a,b) \le \binom{a+b-2}{a-1}$.

\item 
(10 points) Use the result $R(a,b)\le \binom{a+b-2}{a-1}$ to get an asymptotic upper
bound on $R(k)$ that is LESS THAN $2^{2k-1}$. 
\end{enumerate}

\vfill 

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item 
(30 points)

{\bf Notation} $\N^{\ge 2}$ means the set $\{2,3,4,\ldots\}$. 

{\bf Def} Let $G=(V,E)$ be a graph. $D\subseteq V$ is a {\it dominating set (DS)} 
if 
$$(\forall u\in V)[u\in D \vee (\exists v\in D)[(u,v)\in E].$$

Every graph has a DS of size $n$: $D=V$. We do better!

You will prove: {\it There exists a function $\alpha\colon \N^{\ge 2} \into (0,1)$ such that, 

a) For every $d\in\in\N^{\ge 2}$, $\alpha(d+1)<\alpha(d)$ 
(so $\alpha(d)$ is \textbf{STRICTLY DECREASING}).

b) For every graph with min degree $\ge d$ there is a dominating set of size $\le \alpha(d)n$.

}

On the next page we will state the theorem with the function $\alpha$ and sketch the proof.
YOU will fill in the details and find a function $\alpha$ that works. 
We guide this with a series of embedded questions.

\newpage 

\noindent
{\bf Thm} 
There exists a function $\alpha\colon \N^{\ge 2}\into (0,1)$ such that the following hold:
\begin{itemize}
\item
$\alpha$ is strictly DECREASING.
\item
If $G=(V,E)$ is a graph on $n$ vertices with min degree $\ge d$ then
$G$ has a dominating set of size $\le \alpha(d)n$. 
\end{itemize} 

\noindent
{\bf Proof Sketch} Let $p$ be a probability to be determined by YOU later.

Pick $X\subseteq V$ as follows: For every $v\in V$ choose $v$ with probability $p$. 

\smallskip

\begin{enumerate}
\item 
(0 points but you need it for later)
What is $E(|X|)$? It will be a function of $n,p$. 

\item 
(0 points but you need it for later)
Let $Y\subseteq V-X$ be the vertices that DO NOT have an edge to an element of $X$.
Formally

$$Y= \{ y\in V-X \colon (\forall x\in X)[(x,y)\notin E].$$

Give an upper bound on $E(|Y|)$. It will be a function of $n,d,p$.
Note that $X\cup Y$ is a dominating set. We later pick $p$ so that $|X\cup Y|$ is small.

\item 
(0 points but you need it for later)
What is $E(|X\cup Y|)$? (Hint: This is very easy by the linearity of expectation.) 

\item 
(30 points) 
Pick $p$ to make $E(|X\cup Y|)$ smaller than $n$ 
then give the function $\alpha$. 
(Hint: Find an upper bound on $E(|X\cup Y|)$ and minimize that bound. 
Use that $(1-p)\le e^{-p}$.)


\noindent
{\bf End of Proof of Sketch} 
\end{enumerate} 


\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(35 points) 

\begin{enumerate}
\item 
(0 points but you need to do it for the rest of the problem)
Write a program that will, given $n$, 
generate a random 2-coloring of
$\binom{[n]}{2}$ by, for each edge, color it RED with prob $\frac{1}{2}$
and BLUE with prob $\frac{1}{2}$. 

\item 
(0 points but you need to do it for the rest of the problem)
Write a program that will, given $n$ and a 2-coloring of $\binom{[n]}{2}$,
count how many mono $K_3$'s there are. 

\item
(0 points but you need to do it for the rest of the problem)
This problem just puts the two programs together. 
Write a program that will, given $n$, 
generate a random 2-coloring of
$\binom{[n]}{2}$ by, for each edge, color it RED with prob $\frac{1}{2}$
and BLUE with prob $\frac{1}{2}$ and then OUTPUTS the number of mono $K_3$'s.

\item 
(0 points but you need to do it for the rest of the problem)
This problem mostly uses the last program. 
Write a program that will, given $n$, 
run the last program 100 times and gather up the number-of-triangles. 
Then just output
the MIN and the MAX. 

\item 
(35 points)
Write a program that outputs a table with

\begin{itemize}
\item
$n$ going from 4 to 30
\item
Min number of mono $K_3$'s from last program.
\item
Max number of mono $K_3$'s from last program.
\item
How much bigger is the Max from what we are guaranteed by the theorems in class.
We call this {\it over}. 
\end{itemize} 

Here is the format of the table (I made up the numbers and only give the
first 3 rows):

\begin{tabular}{|c|c|c|c|}
\hline 
$n$ & min & max  & over \cr 
\hline 
4   & 1 &   2    & 2 \cr 
5   & 1 &   2    & 1 \cr 
6   & 2 &   8    & 3 \cr 
\hline
\end{tabular} 

\item
(0 points) Make a conjecture about what happens for a random coloring. 

\end{enumerate}


\end{enumerate}

\end{document}

