\documentclass[12pt]{amsart}
\usepackage{amsmath}
\usepackage{graphicx, epic,eepic, pstricks}

\setlength{\textwidth}{15.5cm} \setlength{\headheight}{0.5cm}
\setlength{\textheight}{21.5cm} \setlength{\oddsidemargin}{0.25cm}
\setlength{\evensidemargin}{0.25cm} \setlength{\topskip}{0.5cm}
\setlength{\footskip}{1.5cm} \setlength{\headsep}{1cm}
\setlength{\topmargin}{0.5cm}

% Fuzz -----------------------------------------------------------
\hfuzz5pt % Don't bother to report overfull boxes < 5pt
% MATH -----------------------------------------------------------
\DeclareMathOperator{\RE}{Re} \DeclareMathOperator{\IM}{Im}
\DeclareMathOperator{\ess}{ess}
\newcommand{\eps}{\varepsilon}
\newcommand{\To}{\longrightarrow}
\newcommand{\h}{\mathcal{H}}
\newcommand{\s}{\mathcal{S}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\J}{\mathcal{J}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\W}{\mathcal{W}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\BOP}{\mathbf{B}}
\newcommand{\BH}{\mathbf{B}(\mathcal{H})}
\newcommand{\KH}{\mathcal{K}(\mathcal{H})}
\newcommand{\Real}{\mathbf{R}}
\newcommand{\Complex}{\mathbf{C}}
\newcommand{\Field}{\mathbf{F}}
\newcommand{\RPlus}{\Real^{+}}
\newcommand{\Poly}{\mathcal{P}}
\newcommand{\EssD}{\mathcal{D}}
\newcommand{\Lom}{\mathcal{L}}
\newcommand{\States}{\mathcal{T}}
\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\seq}[1]{\left<#1\right>}
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}
\newcommand{\essnorm}[1]{\norm{#1}_{\ess}}
% THEOREM ENV. ------------------------------------------------------------
\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{con}{Conjecture}
\newtheorem{lem}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{defn}{Definition}
\newtheorem{clm}{Claim}
\newtheorem{obs}{Observation}
\newtheorem{conj}{Conjecture}
\newtheorem{prob}{Problem}
%\renewcommand{\thethm}{}  % unnumbered
\pagestyle{empty}
\renewcommand{\baselinestretch}{1.15}
%%% ----------------------------------------------------------------------

\begin{document}
\begin{center}
{\bf Math 432 Homework Twelve}\\
Due: Friday, April 22, 2016
\end{center}

\bigskip

Prove the following statements.  Four points for each. \\

\begin{enumerate}
\item For $n\in N$ and $1\le k\le n-1$, define a square $A^{(k)}$ by $a_{i,j}^k=ki+j \mod n$.  \\
(a) Prove that $A^{(k)}$ is a Latin square if and only if $n$ and $k$ are relatively prime. \\
(b) When $A^{(k)}$ and $A^{(l)}$ are Latin squares, prove that they are orthogonal if and only if $k-l$ is relatively prime to $n$. \\

\item Le $M$ be a Latin square that can be written as $\begin{pmatrix} X & Y\\ Y & X\end{pmatrix}$ with $X$ and $Y$ being Latin squares of odd order.  Prove that $M$ has no transversal, where a transversal is a set of $n$ distinct entries in distinct rows and distinct columns.  Use this to prove that there is no Latin square orthogonal to $M$. \\

\item (i) Determine the index of the set $\{2, 4, 6, 7\}$ in the colex
ordering. (ii) Find the $4$-binomial expansion of the integer $40$.\\


\item Suppose that $m={r\choose k}$. Let $F$ be a family with
minimum shadow among the $k$-uniform families of size $m$ in the
subsets of $[n]$. Prove that $F$ consists of all $k$ subsets among
some $r$ elements. (Hint: apply the Kruskal-Katona Theorem)\\

\item Let $p,r,s,t$ be integers with $2\le p<r$. Suppose also that
$r\le t+1\le s$ or that $t=0$ and $r\le s$. Use Kruskal-Katona
Theorem to prove that every graph with at most ${s\choose
p}+{t\choose p-1}$ cliques of size $p$ has at most ${s\choose
r}+{t\choose r-1}$ cliques of size $r$.  Show that the bound is
sharp.



\end{enumerate}
\end{document}
