Skip to main content
2 of 5
Added example
Timothy Chow
  • 82.7k
  • 26
  • 363
  • 587

Coloring a Ferrers diagram

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.

Timothy Chow
  • 82.7k
  • 26
  • 363
  • 587