9
$\begingroup$

This question is about a possible lacuna in a paper of Greene and Kleitman which Zarathustra Brady made me aware of.

The paper in question is "Longest Chains in the Lattice of Integer Partitions ordered by Majorization" (available online here). In that paper they compute the length of the longest chain in the dominance order on partitions, and more generally give an algorithm for finding the longest chain in any interval of dominance order.

In dominance order we have a cover relation $\lambda \gtrdot \mu$ if and only if $\mu$ is obtained from $\lambda$ by moving a single box in row $i$ to row $i+1$, or by moving a single box in column $i+1$ to column $i$. In the first case, Greene and Kleitman say that $\lambda \gtrdot \mu$ is an H-step (because, perhaps confusingly to modern readers, the box moved one unit horizontally according to their nonstandard scheme of drawing partitions with vertical parts- see Figure 2), and in the second case they say that $\lambda \gtrdot \mu$ is a V-step (because the box moved one unit vertically according to their depiction). Note, as the authors note, that it is possible that $\lambda \gtrdot \mu$ is both an H-step and a V-step (and in fact this is the source of the possible lacuna!).

Greene and Kleitman say that a chain $\lambda^0 > \lambda^1 > \cdots > \lambda^L$ is an H-chain if each step $\lambda^i > \lambda^{i+1}= \lambda^i \gtrdot \lambda^{i+1}$ is an H-step, and similarly say that the chain is a V-chain if each step $\lambda^i > \lambda^{i+1}= \lambda^i \gtrdot \lambda^{i+1}$ is a V-step. Furthermore, they say $\lambda^0 > \lambda^1 > \cdots > \lambda^L$ is an HV-chain if there is some index $i$ such that $\lambda^0 > \cdots > \lambda^i$ is an H-chain, and $\lambda^i > \cdots > \lambda^L$ is a V-chain.

In a crucial lemma of the paper, Lemma 3, they assert that if $\lambda = \lambda^0 > \lambda^1 > \cdots > \lambda^L = \mu$ is any chain in dominance order, then there exists some HV-chain between $\lambda$ and $\mu$ of length at least $L$. The argument they give is: we can assume each step in the chain is a cover relation; we can check that it is true for chains $\lambda_0 > \lambda_1 > \lambda_2$ of length 2; then by repeatedly applying this length 2 case we can convert any chain of length $L$ to an HV-chain of length at least $L$.

But this last point about repeatedly applying the length 2 case seems suspect, for the following reason. Suppose we have a length 3 chain $\lambda_0 > \lambda_1 > \lambda_2 > \lambda_3$ such that $\lambda_0 > \lambda_1$ is a V-step which is not an H-step, $\lambda_1 > \lambda_2$ is both a V- and H-step, and $\lambda_2 > \lambda_3$ is an H-step which is not a V-step. (This situation can arise: $(5,4,3,2) > (4,4,4,2) > (4,4,3,3) > (4,4,3,2,1)$.) Then the problem is that, from the perspective of length 2 subchains, things look fine: $\lambda_0 > \lambda_1 > \lambda_2$ is a V-chain, so is in particular an HV-chain; similarly $\lambda_1 > \lambda_2 > \lambda_3$ is an H-chain, so in particular is an HV-chain. But $\lambda_0 > \lambda_1 > \lambda_2 > \lambda_3$ is evidently not an HV-chain.

Question: Is this a real oversight in the paper of Greene-Kleitman? If so, is Lemma 3 indeed true, and can the proof be repaired?

$\endgroup$
3
  • 1
    $\begingroup$ Have you tried contacting Curtis Greene directly? $\endgroup$ Nov 30, 2019 at 16:03
  • $\begingroup$ @TimothyChow: I have not. $\endgroup$ Nov 30, 2019 at 16:15
  • 1
    $\begingroup$ This does look like case that was not considered in the proof. It is not, though, a counterexample to the lemma (which I know you did not claim): The only H move from 5432 is (in their notation) $[4 \rightarrow 5]$ to 54311, then $[3 \rightarrow 4]$ to 54221, $[2 \rightarrow 3]$ to 53321, and finally $[1 \rightarrow 2]$ to 44321. These are all simultaneously H and V steps, so call it an H-chain or a V-chain. $\endgroup$ Feb 3, 2020 at 15:45

0

Your Answer

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

Browse other questions tagged or ask your own question.