\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}
\providecommand{\abs}[1]{\lvert#1\rvert}
\providecommand{\norm}[1]{\lVert#1\rVert}

\newtheorem{thm}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{fact}[thm]{Fact}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{eg}{Example}
\newtheorem{ex}{Exercise}
\newtheorem{defi}{Definition}
\newtheorem{hw}{Problem}
\newenvironment{sol}
  {\par\vspace{3mm}\noindent{\it Solution}.}
  {\qed}

\newcommand{\ov}{\overline}
\newcommand{\cb}{{\cal B}}
\newcommand{\cc}{{\cal C}}
\newcommand{\cd}{{\cal D}}
\newcommand{\ce}{{\cal E}}
\newcommand{\cf}{{\cal F}}
\newcommand{\ch}{{\cal H}}
\newcommand{\cl}{{\cal L}}
\newcommand{\cm}{{\cal M}}
\newcommand{\cp}{{\cal P}}
\newcommand{\cz}{{\cal Z}}
\newcommand{\eps}{\varepsilon}
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\dist}{\mbox{\rm dist}}
\newcommand{\bn}{{\mathbf N}}
\newcommand{\br}{{\mathbf R}}
\newcommand{\bz}{{\mathbf Z}}
\newcommand{\expe}{{\mathsf E}}
\newcommand{\prob}{{\mathsf{Pr}}}

\setlength{\parindent}{0pt}
%\setlength{\parskip}{2ex}
\newenvironment{proofof}[1]{\bigskip\noindent{\itshape #1. }}{\hfill$\Box$\medskip}

\begin{document}

$\;$\hfill Due: 2012/11/28 before class

\begin{center}
{\LARGE\bf Homework 10}
\end{center}

Note: When you want to apply the  L.L.L.. Specify clearly what is the probability space; what are the events;
how many events do you have; what is the dependency graph you want to use and why it satisfies the definition
of a dependency graph; and show your calculations about the probabilities and degrees.

\begin{hw}
Given a graph $G = (V, E)$, we uniformly randomly pick $\sigma$, a permutation of $V$.
For each vertex $v \in V$, call $v$ a seed if $v \prec_\sigma u$ for any
$uv \in E$; and define $X_v$ to be the indicator random variable for the event that $v$
is a seed. And define $X = \sum_{v \in V} X_v$ to be the number of seeds in an outcome.

(a) If $G$ is the graph on 6 vertices that consists of two vertex-disjoint triangles,
what is $\expe(X)$, and what is the probability of $X = \expe(X)$?

(b) If $G$ is the cycle $C_6$,
what is $\expe(X)$, and what is the probability of $X = \expe(X)$?

\end{hw}

\begin{hw}
For any $n > 2$, show an example of a probability space and $n$ events
where any $n-1$ of them are mutually independent, but the $n$ events
are not mutually independent.
\end{hw}

\begin{hw}
Fix some integer $d \geq 1$. Let $G = (V, E)$ be a graph and for each $v$ we have a set of candidate colours $S(v)$ where $|S(v)| = 10d$. Suppose that for each
$v \in V$ and each candidate $c \in S(v)$, there are at most $d$ vertices $u$ such that $uv \in E$ and $c \in S(u)$. Prove that $G$ has a proper colouring where each vertex $v$ is coloured by one of its candidates in $S(v)$. (Hint: Finding the right collection of events will bring a short solution.)
\end{hw}


\begin{hw} Let $k \geq 10$ and $n = \lfloor 2^k / (10k) \rfloor$. A subset $X \subseteq [n]$
is called a {\em Za} if the elements of $X$ form an arithmetic progression of length $k$.

{\em (a).} Show that for any Za, there are less than $1.25kn$ other Za's share some common points
with it.

{\em (b).} Prove that we can color each element of $[n]$ with yellow and blue such that
no Za is monochromatic.
\end{hw}

\end{document}

