26
$\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.

EDIT (9 August 2024): With Mark Tiefenbruck, I have been able to prove some partial results, which have now been posted to the arXiv: The Latin Tableau Conjecture. I'm now pretty convinced that the answer to the question is yes—in fact, I now feel that this is one of the most interesting conjectures I've ever come up with—but I can't prove it. Our main result is that there does exist a coloring $c$ such that for every proper coloring $c'$, $n_1(c) + \cdots + n_i(c) \ge n_1(c') + \cdots + n_i(c')$ for $1\le i\le 4$. In particular, the answer to the question in domotorp's comment is yes. Unfortunately, our method is case-based and gets increasingly cumbersome for larger values of $i$.

Improve this question
$\endgroup$
24
  • 1
    $\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
    Commented 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$
    – Martin Rubey
    Commented Apr 18, 2017 at 13:55
  • 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$
    – Timothy Chow
    Commented Apr 19, 2017 at 15:30
  • 1
    $\begingroup$ @Tri, I haven't reconstructed the test for the lattice property, but the largest for partitions of 16 has 87 vertices. Code, data. $\endgroup$
    – Peter Taylor
    Commented Jun 12 at 11:44
  • 1
    $\begingroup$ @domotorp I can now say that the answer to your question is yes. See the latest edit to my question. $\endgroup$
    – Timothy Chow
    Commented Aug 9 at 4:59

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .