\documentclass[12pt]{article}
%\usepackage{amssymb,euscript}
\textheight=9in
\topmargin=0in
\textwidth=6.5in
\oddsidemargin=0in
\let\noind=\noindent
\def\Pr{\textbf{Pr}}

\begin{document}
\pagestyle{empty}
\begin{center}
{\bf \large \textbf{CSC 2427} \hfill Assignment \#1 Answers}\\[3mm]
{\bf \large Behdad Esfahbod \hfill Student \# 993505827}\\
\hrulefill
\end{center}
\begin{enumerate}

\item % 1
If there is no giant component, then a.s.{} there is no
$d$-cycle.  So $q\geq \frac1n$.  And if there is a giant
component, there are lots of cycles:
$p=(1+\epsilon)q=\frac{1+\epsilon}n$
$$
E[C]=E[\# \mbox{cycles}]=\sum_{i=3}^{n} \frac1i i!{n\choose i}p^i
\simeq \sum_{i=3}^n \frac1i (\frac ie)^i\sqrt{2\pi i} (\frac{en}i)^i
(\frac{1+\epsilon}n)^i
= \sum_{i=3}^n \sqrt{\frac{2\pi}i} (1+\epsilon)^i
$$

Which when $\epsilon$ is a positive constant, tends to infinity,
so there is an $n$ after which there are at least $dn$ cycles,
which in turn means there exists a vertex that is in at least
$d$ cycles.  It remains to show the concentration.
%By adding
%each edge, the total number of new cycles that become available
%is $\sum_{i=1}^{n-2} i! {n-2\choose i}$.  There are fewer than $n^2$
%edges.  Now we can apply Azuma's inequality to bound the
%probability of having too few cycles:
%$$
%\Pr(|C-E(C)|\geq \frac{E(C)}2) <
%2e^{-E(C)^2/2(n^2\sum_{i=1}^{n-2} i! {n-2 \choose i})}
%$$
%
%Which would tend to be small as p.

%\item % 2

\item % 3
The way I show this is pretty much like the way we did in class
for regular graphs.  Consider a vertex coloring of the
hyptergraph.  All vertices of a certain color form an independent
set.  So if $A$ is the size of the largest independent set of the
graph, then $\chi \ge \frac{n}{A}$.  Now we count the expected
number of independent sets of size $A$:
$$
E[X]=E[\mbox{\# ind.~sets~of~size} A] = {n\choose A}2^{-A\choose3}
\simeq \left(\frac{en}{A}\right)^A 2^{-A^3/6}
\simeq \left(\frac{en}{A.2^{A^2/6}}\right)^A
$$

The value of $X$ would become $\Theta(1)$ around $A=\sqrt{6\lg n}$.
For $A=(1-\epsilon)\sqrt{6\ln n}$, the value of X becomes
$n^{A\epsilon}$ that would eventually become far greater than $n^2$.

But we cannot show concentration for $X$ using Azuma inequality.
For this, lets consider the expected number of independent sets
of size $A$ that no two share three vertices.  We can estimate
this value called $Y$ by subtracting from $X$ the number of two
independent sets of size $A$ that do share three vertices ($Z$):
\begin{eqnarray*}
E[Z]&=&E[\mbox{\# pairs of ind.~sets of size} A \mbox{that share three
    vertices}]
\\&\leq& {n\choose A}{A\choose3}{n-A\choose A-3}
   {\left(\frac12\right)}^{{A\choose3}+{A\choose3}-1}
\\&\leq& E(X).\frac{A^3}{6}\left(\frac{en}{A}\right)^{A-2}
   {\left(\frac12\right)}^{A(A-1)(A-2)/6}
\\&\simeq& E(X).\frac{A^3}{6}\left(\frac{en}{A.2^{A^3/6}}\right)^{A-2}
\end{eqnarray*}

The part after $E(X)$ is $o(1)$ and so would become less than
$\frac12$ soon.  Then as $Y \geq X-Z$ we get $E(Y)\geq
E(X)-E(Z)$:
$$E(Y)\geq \frac{E(X)}{2}.$$

Now we can show concentration for $E(Y)$ using Azuma's
inequality:
$$
\Pr(|Y-E(Y)|\geq t)<2e^{-t^2/2n}
$$

By now we have shown that for $f(n)=\frac{n}{\sqrt{6\lg n}}$, the
chromatic number of the random hypergraph is greater than
$f(n)(1+o(1))$.  Now we try to achieve this bound by coloring the
hypergraph.  We color one color at a time.  At each step, we take
an independent set of size $A$ and color all vertices in it with
a single color.  At each step there is a small probability of
failure $\delta$.  We keep doing this until the set of remaining
vertices is as small as $\frac{n}{\lg n}$.  Then we color each
remainig vertex with its own color.  Since the probability
$\delta$ of failure in each step is bounded by $\Pr(|Y-E(Y)| \geq
E(Y))<2e^{-E(Y)^2/2n} < e^{-n}$, then repeating this for
less than $n$ times, still gives us a fairly small probability of
failure ($<ne^{-n}$).  The expected number of total colors would be bounded by
$\frac{n}{\sqrt{6\lg n}}(1+o(1))$.

\end{enumerate}
\end {document}