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



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

\item  Solve all problems.
\end{itemize}


\noindent{\bf 1.} Given a graph $G$ with $\chi(G)=n$ and a proper coloring $f:V(G)\to [n]$, prove that
for any color $i\in [n]$, there exists a vertex of color $i$ adjacent to a vertex of every other color.


\bigskip


\noindent{\bf 2.} Let $\mathcal{F} \subseteq 2^{[n]}$ be such that
\begin{itemize}
\item $|A|$ is even for all $A\in \mathcal{F}$, and
\item $|A\cap B|$ is even for all distinct $A,B\in \mathcal{F}$.
\end{itemize}
Prove that $\mathcal{F}\le 2^{n/2}$.



\bigskip

\noindent{\bf 3.} Let $m$ red clubs $R_1,...,R_m\subseteq [n]$ and $m$ blue clubs $B_1,...,B_m\subseteq [n]$ be such that
\begin{itemize}
\item  $|R_i\cap B_i|$ is odd for every $i$, and
\item $|R_i\cap B_j|$ is even for every $i\neq j$.
\end{itemize}
Show that $m\le n$. And then answer the question if you can weaken the second condition to all $i<j$ (explain why).



\bigskip

\noindent{\bf 4.} ($s$-distance sets.) Let $s\ge 3$ be an integer. Let $a_1,a_2,...,a_m$ be points in $\mathcal{R}^n$ and suppose that the pairwise distances between them take at most $s$ values. Prove that $m\le \binom{n+s+1}{s}$.


\bigskip


\noindent{\bf 5.} Construct a two-distance set of size $\binom{n+1}{2}$ in some $\mathbb{R}^n$.


\bigskip

\noindent{\bf 6.} Prove that among any $2^{k-1}+1$ vectors in $\mathbb{F}_2^n$, there are $k$ vectors which are linearly independent.





\end{document}
