\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: 2011/12/07 before class

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

The first problem is related to the topic we will cover in the next week.

\begin{hw} Let $n=10$, consider subsets of $[n]$.

(a) Are there 200 subsets $(A_1, A_2, ..., A_{200})$ such that $A_i \not\subseteq A_j$ for any $i \neq j$?

(b) Are there 100 subsets $(B_1, B_2, ..., B_{100})$ such that $|B_i| = 5$ for all $i$, and $B_i \cap B_j \neq \emptyset$ for all $i < j$?
\end{hw}

The second problem says that, in order to check the regularity of a pair, it is enough to check the subsets
of size just above the threshold.

\begin{hw}
Let $G = (V, E)$ be a graph and $(X, Y)$ be a pair of nonempty disjoint subset of $V$.
Let $\epsilon$ be a constant such that $1 > \epsilon > 0$. Let $t_1 = \lceil \epsilon |X| \rceil$
and $t_2 = \lceil \epsilon |Y| \rceil$. Prove that,
if $|d(A, B) - d(X, Y)| < \epsilon$ for any pair $(A, B)$ where $A \in \binom{X}{t_1}$ and $B \in \binom{Y}{t_2}$,
then $(X, Y)$ is $\epsilon$-regular.
\end{hw}

The last problem is a weaker version of Erd\"os-S\'os conjecture.

\begin{hw} Let $G$ be a graph with $n$ vertices and at least $(k-1)n$ edges.

(a). Prove that $G$ has a subgraph $G'$ where $\delta(G') \geq k$.

(b). Prove that $G$ contains every tree with $k$ edges.
\end{hw}

\end{document}

