Wide partition conjecture

Importance: Medium ✭✭
Subject: Combinatorics
Recomm. for undergrads: no
Posted by: tchow
on: September 24th, 2008

\begin{conjecture} An integer partition is wide if and only if it is Latin. \end{conjecture}

An integer partition $\lambda$ is \emph{wide} if $\mu \ge \mu'$ for every subpartition $\mu$ of $\lambda$. (Here $\mu'$ denotes the conjugate of $\mu$, $\ge$ denotes dominance or majorization order, and a subpartition of $\lambda$ is a submultiset of the parts of $\lambda$.) An integer partition $\lambda$ is \emph{Latin} if there exists a tableau $T$ of shape $\lambda$ such that for every $i$, the $i$th row of $T$ contains a permutation of $\{1,2,\ldots,\lambda_i\}$, and such that every column of $T$ contains distinct integers. It is easy to show that if $\lambda$ is Latin then $\lambda$ is wide, but the converse remains open.


*[CFGV] Timothy Y. Chow, C. Kenneth Fan, Michel X. Goemans, Jan Vondrak, \href[Wide partitions, Latin tableaux, and Rota's basis conjecture]{http://alum.mit.edu/www/tchow/wide.pdf}, Advances Appl. Math. 21 (2003), 334-358.

* indicates original appearance(s) of problem.