\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{multicol}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}


\project{1: Latin Squares}{Weeks 1-10}

An order-$n$ \textbf{Latin square} is a $n \times n$ array filled with the symbols $\{1,2,\ldots n\}$, such that no symbol is repeated in any row or column.  Here are a few Latin squares of small orders:
\begin{align*}
\begin{array}{|c|c|}\hline
2 & 1 \\\hline
1 & 2 \\\hline
\end{array}~, \qquad
\begin{array}{|c|c|c|}\hline
1 & 2 & 3\\\hline
2 & 3 & 1 \\\hline
3& 1 & 2 \\\hline
\end{array}~, \qquad
\begin{array}{|c|c|c|c|}\hline
1 & 4 & 3 & 2\\\hline
2 & 3 & 1  & 4\\\hline
4& 1 & 2 & 3\\\hline
3 & 2 & 4 & 1 \\\hline
\end{array}~.
\end{align*}

A \textbf{partial Latin square} is a $n \times n$ array in which cells can either be blank or contain a symbol $\{1, \ldots, n\}$, such that no symbol occurs twice in any row or column.  A Latin square $L$ is called a \textbf{completion} of a partial Latin square $P$ if $L$ and $P$ agree on all of $P$'s nonblank entries.

Some partial Latin squares have completions:
\begin{align*}P = 
\begin{array}{|c|c|c|}
\hline & 2 &  \\
\hline 3 & 1 & 2 \\
\hline &  & \\
\hline
\end{array} \longmapsto L = 
\begin{array}{|c|c|c|c|}
\hline 1& 2 & 3\\
\hline 3 & 1 & 2 \\
\hline2& 3 & 1\\
\hline
\end{array}
\end{align*}

Others do not:
\begin{align*}
P = \begin{array}{|c|c|c|}
\hline 1 &  & \\
\hline  & 1 & \\
\hline &  & 2 \\
\hline
\end{array} \textrm{ has no completion.}
\end{align*}

Determining what kinds of partial Latin squares have completions is an open question in many situations! Here are some known results:
\begin{itemize}
\item (Hall, 1949:) A \textbf{Latin rectangle} is a partial Latin square $P$ where the first $k$ rows of $P$ are filled and the rest are blank.   All Latin rectangles can be completed.
\item (Smetaniuk, 1981:)  If $P$ is a partial latin square with $\leq n-1$ filled cells, $P$ can be completed. 
\item (Buchanan, 2007:) If $P$ is a $n \times n$ partial Latin square where precisely 2 rows and columns of $P$ are filled, $P$ can be completed.
\end{itemize}

A question I spent part of my dissertation studying is the following: Call a $n \times n$ partial Latin square \textbf{$\kern-2pt\epsilon$-sparse} if at most $\epsilon n$ of the entries in any row, column, or symbol are not blank.  It is conjectured that all $1/4$-sparse partial Latin squares are completable; in my dissertation I proved that all $10^{-4}$-dense partial Latin squares are completable.

This result is improvable, in many different ways.  Students on this project will attempt to find such improvements!







\end{document}