Home » Subject » Combinatorics

Wide partition conjecture

Importance: Medium ✭✭
Author(s): Chow, Timothy Y.
Taylor, Brian D.
Subject: Combinatorics
Keywords:
Recomm. for undergrads: no
Posted by: tchow
on: September 24th, 2008
Conjecture   An integer partition is wide if and only if it is Latin.

An integer partition $ \lambda $ is 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 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.

Related problems

Rota's basis conjecture

Bibliography

*[CFGV] Timothy Y. Chow, C. Kenneth Fan, Michel X. Goemans, Jan Vondrak, Wide partitions, Latin tableaux, and Rota's basis conjecture, Advances Appl. Math. 21 (2003), 334-358.


* indicates original appearance(s) of problem.
add new comment