21
$\begingroup$

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.

$\endgroup$
16
  • $\begingroup$ 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')$? $\endgroup$
    – domotorp
    Apr 18, 2017 at 8:11
  • 1
    $\begingroup$ 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) $\endgroup$ Apr 18, 2017 at 13:55
  • $\begingroup$ In case you know of a more sensible statistic, please let me know. $\endgroup$ Apr 18, 2017 at 14:02
  • $\begingroup$ 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*} $\endgroup$ Apr 19, 2017 at 7:15
  • 1
    $\begingroup$ @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. $\endgroup$ Apr 19, 2017 at 15:30

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.