Outline Rectangles, Allocations, and Latin Young Diagrams

Abstract

A Young diagram is \emph{Latin} if there is an assignment of integers to its cells so that each row $i$ of length $l_i$ is populated by the numbers $1,\dots ,l_i$, and the numbers in each column are distinct. A Young diagram is called \emph{wide} if any subdiagram, formed by a subset of its rows, dominates its conjugate. Chow et al. [Advances in Applied Mathematics, 31, 2003] conjectured that any wide Young diagram is Latin. We introduce a notion of an \emph{allocation} which can be thought of as a coarse attempt at finding a Latin filling for a Young diagram. Using a theorem of Hilton, we prove that a Young diagram has an allocation if and only if it is Latin. This enables us to prove Chow et al.'s conjecture for Young diagrams with three distinct row lengths.