\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.15in}
\setlength{\evensidemargin}{.15in}
\setlength{\textwidth}{6.2in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.6in}


\input{preamble.tex}

\begin{document}

\homework{1: Latin Squares}{Due Tuesday, week 2, at the start of class}

Try some of the problems below!  As always, work on problems here until you've spent at least 90 minutes on this set.  Show your work, so that I can see that you've spent time/effort on this!

This week's HW centers around the following idea:
 \begin{definition}
A \textbf{partial latin square} of order $n$ is a $n \times n$ array where each cell is filled with either blanks or symbols $\{1, \ldots n\}$, such that no symbol is repeated twice in any row or column. 
\end{definition}
\begin{exmp}
Here are a pair of partial $4 \times 4$ latin squares:
\begin{align*}
\begin{array}{|c|c|c|c|}\hline
  &  &  & 4\\\hline
 2 &  & &   \\\hline
 3 & 4 &  & \\\hline
 4 & 1 & 2 & \\\hline
\end{array} \qquad
\begin{array}{|c|c|c|c|}\hline
 1&  &  & \\\hline
  & 1 & &   \\\hline
  &  & 1 & \\\hline
  &  &  & 2 \\\hline
\end{array}
\end{align*}
\end{exmp}

The most obvious question we can ask about partial latin squares is the following: when can we complete them into filled-in latin squares?  There are clearly cases where this is possible: the first array above, for example, can be completed as illustrated below.
\begin{align*}
\begin{array}{|c|c|c|c|}\hline
  &  &  & 4\\\hline
 2 &  & &   \\\hline
 3 & 4 &  & \\\hline
 4 & 1 & 2 & \\\hline
\end{array} \mapsto 
\begin{array}{|c|c|c|c|}\hline
 1 & 2 & 3 & 4\\\hline
 2 & 3 & 4 & 1\\\hline
 3 & 4 & 1 & 2\\\hline
 4 & 1 & 2 & 3\\\hline
\end{array} 
\end{align*}

However, there are also clearly partial Latin squares that cannot be completed.  For example, if we look at the second array
\begin{align*}
\begin{array}{|c|c|c|c|}\hline
 1&  &  & \\\hline
  & 1 & &   \\\hline
  &  & 1 & \\\hline
  &  &  & 2 \\\hline
\end{array},
\end{align*}
we can pretty quickly see that there is no way to complete this array to a Latin square: any $4 \times 4$ Latin square will have to have a 1 in its last column somewhere, yet it cannot be in any of the three available slots in that last column, because there's already a 1 in those three rows.
\begin{enumerate}
\item For any $n$, create a partial $n\times n$ Latin square that contains $n$ symbols, that cannot be filled to a complete Latin square.
\item A partial Latin square is called \textbf{critical} if it has a completion to exactly one other Latin square.  For example, $\begin{array}{|c|c|}\hline 1 & \hphantom{1} \\\hline & \\\hline\end{array}$ is a critical partial Latin square, as it can be completed to only one Latin square, $\begin{array}{|c|c|}\hline 1 & 2 \\\hline2 & 1\\\hline\end{array}$.  

Find the smallest $4 \times 4$ critical Latin square.

\item (Open / my research!)  For any constant $\epsilon > 0$, a  partial $n \times n$ Latin square is called $\epsilon$-sparse if it contains at most $\epsilon n$ entries in any row or column, and also no symbol is used more than $\epsilon n$ many times.  

Show that any $1/4$-dense partial Latin square is completable.

\end{enumerate}

\end{document}