
\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 5}
\end{center}



\begin{itemize}
\item The due is on Tuesday, October 25, at beginning of the class.

\item  Solve all problems.
\end{itemize}

\noindent{\bf 1.} 
Let $G$ be a graph such that for any two non-adjacent vertices $u,v$, it holds that $N_G(u)=N_G(v)$. Prove that $G$ must be a {\it complete multipartite graph}
(i.e., $V(G)$ can be partitioned into $V_1, V_2,...,V_k$ for some $k\ge 2$ such that for any $u\in V_i, v\in V_j$ where $i\neq j$, we have $uv\in E(G)$).


\bigskip

\noindent{\bf 2.} Let $n>0$ be an even integer. Let $\mathcal{F}\subset 2^{[n]}$ be a family of subsets of $[n]$ such that $\mathcal{F}$ contains no four distinct sets $A,B,C,D$ satisfying $A\subset B\subset C\subset D$. Show that $|\mathcal{F}|\le 3\binom{n}{n/2}.$

\bigskip

\noindent{\bf 3.} Recall that in the second proof of Sperner's Theorem we define an equivalence $\sim$ on the family $2^{[n]}$, by letting $M\sim M'$ hold if and only if both $M$ and $M'$ have the same partial pairing of their sequences.

Prove the claim that each equivalence class indeed is a symmetric chain.


\bigskip


\noindent{\bf 4.} Show that the set families $\binom{X}{\lfloor n/2\rfloor}$ and $\binom{X}{\lceil n/2\rceil}$ are the only independent systems on an $n$-element set $X$ with the largest possible number of sets.

\bigskip


\noindent{\bf 5.} Let $X$ be an $n$-element set and let $S_1,S_2,...,S_n$ be subsets of $X$ such that $|S_i\cap S_j|\le 1$ for any $i\neq j$.
Prove that there exists some subset $S_i$ with $|S_i|\le C\sqrt{n}$, for absolute constant $C$ (independent of the choice of $n$).



\bigskip

\noindent{\bf 6.} Show that if a graph $G$ on $n$ vertices does not contain $K_{s,t}$ as a subgraph, then it has at most $C\cdot n^{2-1/s}$ edges for some absolute constant $C$ only depending on $t$ and $s$.

\bigskip

\noindent{\bf 7.} A set $S$ is {\it sum-free} if no elements $x,y,z$ such that $x+y=z$. Let $S$ be a sum-free subset of $[n]$, where $n$ is even.
Prove that $|S|\le n/2$. \\
{\bf Extra points.} Characterize all sum-free subsets $S$ of $[n]$ with $|S|=n/2$.










\end{document}
