\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math571}{Homework 6}{Due April 29, 2013}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve 5 of the following 6 problems.  See the course syllabus and the Homework Webpage on the course website for general directions and guidelines.

\begin{enumerate}
\item{} [CM 10.1.12] Given positive integers $p$ and $q$, let $f(p,q)$ be the largest $m$ such that there is some set of $m$ distinct integers in the interval $[-p, q]$ not containing three integers that sum to 0.  Show that $1+\max\{p,q\} \le f(p,q) \le 2+\max\{p,q\}$.  (Note: it is possible to show that $f(p,q) = 1+\max\{p,q\}$ except when $p$ and $q$ are the same even integer, in which case $f(p,q) = 2+\max\{p,q\}$.)

\item{} [CM 10.1.30] Place $n$ points on a circle.  Let $G_{n,k}$ be the $2k$-regular graph defined on these points by joining each point to the $k$ nearest points in each direction on the circle.  For example, $G_{n,1}$ is the $n$-vertex cycle $C_n$, and $G_{7,2}$ appears below.  For $k\ge 2$, prove that $\chi(G_{n,k}) > k+2$ if $n=k(k+1)-1$ and $\chi(G_{n,k}) \le k+2$ if $n\ge k(k+1)$.
\begin{center}
\begin{tikzpicture}[rotate=90]
	\plotcircleverts{V}{7}{1.5}
	\begin{scope}[every path/.style={edge}]
		\drawcycle{V}{7}
		\draw (V1) -- (V3) -- (V5) -- (V7) -- (V2) -- (V4) -- (V6) -- (V1) ;
	\end{scope}
\end{tikzpicture}
\end{center}

\item{} [CM 10.2.9] Let $S$ be a set of $R(m,m; 3)$ points in the plane no three of which are collinear.  Prove that $S$ contains $m$ points that form a convex $m$-gon.

\item{} [CM 10.2.25] The graph $mK_2$ is the $1$-regular graph on $2m$ vertices.  (The notation $mK_2$ is used since this graph is formed from $m$ disjoint copies of $K_2$.)  Prove that $R(mK_2, mK_2) = 3m-1$.

\item{} [CM 10.2.31] Let $G$ be an $n$-vertex graph with $m$ edges.  For each vertex $v$ in $G$, let $d(v)$ be the degree of $v$.
\begin{enumerate}
	\item Prove that if $\sum_{v\in V(G)} \binom{d(v)}{2} > \binom{n}{2}$, then $G$ contains a $4$-cycle.
	\item Prove that if $m > \frac{n}{4}(1+\sqrt{4n-3})$, then $G$ contains a $4$-cycle.  (Note: in the language of Tur\'an theory, this shows that $\mathrm{ex}(n; C_4) \le \frac{n}{4}(1+\sqrt{4n-3}) \le (2n^{3/2} + n)/4$.)  (Hint: let $f(x) = x(x-1)/2$.  Since $f''(x) > 0$, a convexity argument shows that subject to $x_1 + \cdots + x_k = t$, the sum $f(x_1) + \cdots + f(x_k)$ is minimized when $x_1 = x_2 = \cdots = x_k = t/k$.  You do not need to prove the convexity result in your homework, but you should try to prove it for yourself at least for the case $g(x)=x^2$.)
	\item Recall that $R_k(C_4)$ is the least integer $n$ such that every $k$-edge-coloring of $K_n$ contains a monochromatic copy of $C_4$.  Prove that $R_k(C_4) \le k^2 + k + 2$.  (Comment: using difference sets, there is a lower bound of $k^2 - k + 2$.)
\end{enumerate}

\item{} [CM 11.2.\{4,5,12\}]  In each of the following, prove your answer is correct.
\begin{enumerate} 
	\item Two permutations (in word form) \textbf{intersect} if they agree in some position.  Determine the maximum size of an intersecting family of permutations of $[n]$.
	\item Does every maximal intersecting family of subsets in $[n]$ have size $2^{n-1}$?  
	\item Let $D_n$ be the digraph on $n$ vertices that contains an edge from $u$ to $v$ for each ordered pair $(u,v)$.  An $r$-edge-coloring is \textbf{good} if, for each $u,v,w$ with $u\ne v$ and $v\ne w$ (we allow $u=w$), the color on $uv$ is different from the color on $vw$.  For each $r$, determine the maximum $n$ such that $D_n$ has a good $r$-edge-coloring.  Hint: use Sperner's Theorem (Theorem 11.2.11).
\end{enumerate}

\end{enumerate}
\end{document}
