I've shopped the problem below around a bit and it seems like it might be known, or not that hard to resolve, but so far I've come up empty-handed.

Say that a coloring of the dots of a Ferrers diagram is *proper* if two dots in the same row or column are never assigned the same color. Given a proper coloring $c$, let $n_i(c)$ denote the number of dots of color $i$, where we index the colors so that $n_1(c) \ge n_2(c) \ge n_3(c) \ge \cdots.$ In other words, $n_i(c)$ is the number of dots colored with the $i$th most common color.

Say that a proper coloring $c$ of a Ferrers diagram $D$ is *dominant*
if, for *every* proper coloring $c'$ of $D$ and every $i$,
$$n_1(c) + n_2(c) + \cdots + n_i(c) \ge n_1(c') + n_2(c') + \cdots + n_i(c').$$

Does a Ferrers diagram always have a dominant proper coloring?

If the answer is yes then the proof is probably not going to be easy because it would imply another conjecture that I think is not easy (see this paper for more details). However, perhaps there's an easy counterexample?

**EDIT:**
I should have said that there are easy counterexamples if the condition that the shape be a Ferrers diagram is relaxed. For example, consider the shape below, where again a proper coloring never assigns the same color to two dots in the same row or column.

* * ** *** * *

By coloring the diagonal all one color, we see that there is a coloring $c$ such that $n_1(c)=5$, $n_2(c)=2$, and $n_3(c)=2$. On the other hand it is easy to see that there is also a coloring $c'$ with $n_1(c')=n_2(c')=4$ and $n_3(c')=1$. But it is also easy to see that there is no coloring $c''$ such that $n_1(c'')\ge n_1(c) = 5$ and $n_1(c'')+n_2(c'') \ge n_1(c')+n_2(c') = 8$, so there is no dominant coloring.

**EDIT (18 Nov 2015):** I finally got around to writing a program to check small examples. Assuming no bug in my code, there is no counterexample among the ${20 \choose 10}-1$ nonempty Ferrers diagrams that fit inside a $10\times 10$ box. (I could extend this computation a bit further but I'm not sure I see the point.) Although this obviously doesn't rule out some clever manual construction of a large counterexample, this computation gives me some confidence that the answer to my question is yes. If the answer is indeed yes, then that makes the question simultaneously more interesting and harder to resolve.

11more comments