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.

  • Do you know the answer if we only require $n_1(c)\ge n_1(c')$ and $n_1(c)+n_2(c)\ge n_1(c')+n_2(c')$? – domotorp Apr 18 '17 at 8:11
  • 1
    I just added the number of partitions arising from such colourings to findstat.org/StatisticsDatabase/St000781. (be warned that clicking on "Search for values" currently only produces false positives) – Martin Rubey Apr 18 '17 at 13:55
  • In case you know of a more sensible statistic, please let me know. – Martin Rubey Apr 18 '17 at 14:02
  • Some data: the second column is the list of (transposed!) partitions such that a colouring exists. \begin{align*} [9]&:[9],\\ [8, 1]&:[8, 1],\\ [7, 2]&:[7, 2],\\ [7, 1, 1]&:[7, 2],\\ [6, 3]&:[6, 3],\\ [6, 2, 1]&:[6, 2, 1], [6, 3],\\ [6, 1, 1, 1]&:[6, 3],\\ [5, 4]&:[5, 4],\\ [5, 3, 1]&:[5, 3, 1], [5, 4],\\ [5, 2, 2]&:[5, 2, 2], [5, 3, 1], [5, 4],\\ [5, 2, 1, 1]&:[5, 3, 1], [5, 4],\\ [5, 1, 1, 1, 1]&:[5, 4],\\ [4, 4, 1]&:[4, 4, 1],\\ [4, 3, 2]&:[4, 3, 2], [4, 4, 1],\\ [4, 3, 1, 1]&:[4, 3, 2], [4, 4, 1],\\ [4, 2, 2, 1]&:[4, 3, 2], [4, 4, 1],\\ [3, 3, 3]&:[3, 3, 3] \end{align*} – Martin Rubey Apr 19 '17 at 7:15
  • 1
    @MartinRubey : Say that $\mu$ is a subpartition of $\lambda$ if the multiset of parts of $\mu$ is a submultiset of the multiset of parts of $\lambda$. Then it is not hard to show that $\lambda$ can be colored with multiplicities $\lambda^t$ only if $\mu \ge \mu^t$ for every subpartition $\mu$ of $\lambda$, where $\ge$ denotes dominance order. The "wide partition conjecture" says that this necessary condition is sufficient. This conjecture is still open, and it would follow if every Ferrers diagram has a dominant proper coloring. – Timothy Chow Apr 19 '17 at 15:30

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.