
\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{mathrsfs}
\addtolength{\topmargin}{-.5in} \addtolength{\textheight}{1in}
\addtolength{\oddsidemargin}{-.6in}
\addtolength{\evensidemargin}{-.6in} \addtolength{\textwidth}{1.2in}
\usepackage{latexsym,amsmath,amssymb,amsfonts,epsfig,graphicx,cite,psfrag}
\usepackage{eepic,color,colordvi,amscd}


\def\qed{\hfill \rule{4pt}{7pt}}

\def\pf{\noindent {\it Proof. }}




\pagestyle{plain}


\begin{document}
\begin{center}
    \large{Combinatorics, 2016 Fall, USTC} \\
    {Homework 13}
\end{center}



\begin{itemize}
\item The due is on {\bf Tuesday}, Dec. 27, at beginning of the class.

\item  Solve {all problems}.
\end{itemize}


\noindent{\bf 1.} Let $\{A_1,A_2,...,A_m\}$ be an $L$-intersecting family of subsets of $[n]$, where each $A_i$ is of a constant size, say $k$. Prove that $m\le \binom{n}{|L|}$. (Solve it if you did not do so in HW 10.)

(Hint: beginning with the same proof, and then adding a right number of some polynomials to show that all polynomials are linearly independent.)


\medskip


\noindent{\bf 2.} Suppose $R_1,...,R_m\subseteq [n]$ satisfy that $|R_i|\neq 0 \mod 6$ for every $i$,
and $|R_i\cap R_j|=0 \mod 6$ for every $i\neq j$. Prove that $m\le 2n$.



\bigskip


\noindent{\bf 3.} Derive the following result from Bollob\'as's theorem. Let $A_1,...,A_m$ be subsets of size $a$ and $B_1,...,B_m$ be subsets of size of $b$ such that $|A_i\cap B_i|=t$ for all $i$ and $|A_i\cap B_j|>t$ for all $i\neq j$.
Then $m\le \binom{a+b-t}{a-t}$.

\bigskip

\noindent{\bf 4.}  Let $A_1,...,A_m$ and $B_1,...,B_m$ be finite subsets such that $A_i\cap B_i=\emptyset$ for all $i$ and $A_i\cap B_j\neq \emptyset$ for all $i<j$. If $|A_i|\le a$ and $|B_i|\le b$ for all $i$, then $m\le \binom{a+b}{a}$.







\end{document}
