\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/21 before class

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

\begin{defi}
An {\em independent set} of a hypergraph $\ch = (V, E)$ is a set $S \subseteq V$ such that
$S$ does not contain any hyperedge, i.e. $E \cap 2^{S} = \emptyset$. Define $\alpha(\ch)$
to be the size of the largest independent set in $\ch$.
\end{defi}

\begin{hw}
What is $\alpha(\ch)$ when $\ch$ is the Fano configuration? (See the lecture notes for the definition of this hypergraph.)
\end{hw}

\begin{hw}
Prove that, for any $r$ and $n$ (for simplicity, $r | n$), there is a $r$-uniform hypergraph
$\ch$ with at least $\binom{n}{r} / e^r$ hyperedges, and
\[
\alpha(\ch) \geq n (1 - \frac{1}{r}).
\]
\end{hw}

\begin{hw}
Prove that, for any constant $c_1 > 0$, there is another constant $c_2 > 0$,
such that for any 3-uniform hypergraph $\ch$ with $n$ vertices and $m$ hyperedges
where $m \geq c_1 n$,
\[
\alpha(\ch) \geq \frac{c_2 n \sqrt{n}}{\sqrt{m}}.
\]
\end{hw}

\begin{hw} Let $A$ be a set of $2r+1$ points
\[ A = \{a_1, ..., a_r, b_1, ..., b_r, c\}. \]
Uniformly pick a random permutation $\sigma$ of $A$.
Define the random variables
\[ x := |\{ a_i | a_i \prec_\sigma c\}|,\]
\[ y := |\{ b_i | b_i \prec_\sigma c\}|.\]
Let $0 \leq p \leq 1$ be fixed.

(a) When $r = 1$ and $r = 2$, compute $\expe_\sigma[(1+p)^x (1-p)^y]$.

(b) Prove that $\expe_\sigma[(1+p)^x (1-p)^y] \leq 1$. (Hint:
Let $c_i$ be the number of elements in $\{a_i, b_i\}$ that are
before $c$, $(c_1, ..., c_r)$ is a sequence of 0-1-2 of length
$r$. Partition all the outcomes by conditioning on such sequences.)
\end{hw}

\end{document}
