1
$\begingroup$

Note: I have read somewhere that finding all linear extensions of a partial order is in general a #P-complete problem (which apparently means difficult, and thus no closed form expression), but just because the general problem is difficult does not necessarily mean that specific cases can not be easy. This seemed like a rather specific case.

Question: Given the natural total orderings on the sets $\{1, \dots, M \}$ and $\{1, \dots, N\}$, the product order $\preceq$ on their Cartesian product says that $(m_1, n_1) \preceq (m_2, n_2)$ if and only if $m_1 \le m_2$ and $n_1 \le n_2$. Is there a simple expression for the number of linear extensions of that product order as a function of $M$ and $N$?

What I've tried: In the case that $M=N=2$, this is easy, since there is only one comparison left undecided by the product order, namely $(1,2)$ versus $(2,1)$. Choosing $(1,2) < (2,1)$ corresponds to lexicographical order, and choosing $(2,1) < (1,2)$ corresponds to colexicographical order, and those are the only two possible choices.

(In particular it seems that lexicographical order and colexicographical order are the only choices of linear extension of the product order which are guaranteed to exist for all values of $M$ and $N$.)

I next chose $M=2$ and $N=3$, and found $5$ possible linear extensions of the product order, although the process for doing so seemed to be a lot less straightforward. In particular, I found what seemed to be a subset of rules for a possible "branch and bound" algorithm that could generalize to larger $M$ and $N$, but nothing more straightforward.

Given the complexity of the branch and bound problem even already for one of the simplest possible cases beyond $M=N=2$, I am tempted to think that even this special case of finding linear extensions might also be #P-hard. But I am also inclined to think that I may be missing an obvious combinatorial pattern as well.

Specifically the first branching point was, starting at $(1,1)$, choosing between one down step to $(2,1)$ (corresponding to a choice of $(2,1) < (1,2)$ which in turn implies $(1,3) > (2,1)$ due to the transitivity requirement) or one right step to $(1,2)$ (corresponding to choosing $(1,2) <(2,1)$ and implying nothing else).

On the first branch of the first branching point, (after having went down one step), the only possible move is to go up one step and then right one step. So the next branching point is at $(1,2)$, where again one chooses between going down one step (corresponding to choosing $(2,2)<(1,3)$ and colexicographical order) or going right one step (corresponding to choosing $(1,3)<(2,2)$). Both paths corresponding to the first branch of the first branching point are then completely determined.

On the second branch of the first branching point, (after having went right one step), there are two choices: go right one step to $(1,3)$ (corresponding to a choice of $(1,3)<(2,1)$ which in turn implies $(1,3)<(2,2)$ and thus completely determining the rest of the path -- this is lexicographical order), or go down left to $(2,1)$ (corresponding to a choice of $(2,1)<(1,3)$), and then at $(2,1)$ there are two choices, either to go right one step, corresponding to a choice of $(2,2) < (1,3)$, or to go up right to $(1,3)$, corresponding to a choice of $(1,3) < (2,2)$. At this point all paths are completely determined.

Note that the only comparisons left ambiguous by the requirements of transitivity and being a linear extension of the product order are $(1,2) ? (2,1)$, $(2,1)?(1,3)$, and $(2,2)?(1,3)$, and seemingly not coincidentally each of these choices corresponded to a branch point. However, sometimes the result of resolving one of these choices affects the others via the transitivity requirement, and sometimes it doesn't, making the bound part of "branch and bound" more complicated, and leading to only $5$ possible paths instead of $8$.

More generally, if we write out all of the elements of $\{1, \dots, M\} \times \{1, \dots, N\}$ as if they were the entries of an $M \times N$ matrix, then finding a linear extension of the product order seems to correspond to finding paths through all of the entries of the matrix which satisfy at least the following rules:

Never allowed:
- Going "up left" (i.e. from $(m,n)$ to $(m-k, n-r)$ for some $k,r \in \mathbb{N}$)
- Going "down right" (i.e. from $(m,n)$ to $(m+k, n+r)$ for some $k,r \in \mathbb{N}$)
- Going "left" (i.e. from $(m,n)$ to $(m,n-r)$ for some $r \in \mathbb{N}$)
- Going "up" (i.e. from $(m,n)$ to $(m-k,n)$ for some $k \in \mathbb{N}$)

The prohibitions on going "up left", "left", or "up", makes sense, since such a step would correspond to choosing $(m,n) < (m-k, n-r)$ which contradicts the product order $(m,n) \succeq (m-k,n-r)$ since $m \ge m-k$ and $n \ge n-r$.

The prohibition on going "down right" seemed less straightforward/obvious at first, but I think the explanation is that if one went "down right", then such a move would eventually force someone on the path to either: (i) giving up on visiting all entries of the matrix, or (ii) go left, up, or up left in order to visit any remaining entries.

Allowed only conditionally:

  • Going "down" (i.e. from $(m,n)$ to $(m+1,n)$): provided that the variable RIGHTWARD is equal to $0$. Using this step increments the variable DOWNWARD by $1$ and increments the variable FURTHESTDOWN by $1$.
  • Going "right" (i.e. from $(m,n)$ to $(m, n+1)$: provided that the variable DOWNWARD is equal to $0$. Using this step increments the variable RIGHTWARD by $1$ and increments the variable FURTHERSTRIGHT by $1$.
  • Going "down left" (i.e. from $(m,n)$ to $(m+k, n-r)$ for $k,r \in \mathbb{N}$). Here $r$ seemingly must equal the current value of RIGHTWARD, and after this step RIGHTWARD is reset to $0$. There also seems to be a restriction on $k$, which may also be a function of $m$, but it seems more complicated.
  • Going "up right" (i.e. from $(m,n)$ to $(m-k,n+r)$ for $k,r \in \mathbb{N}$). Here $k$ seemingly must equal the current value of DOWNWARD, and after this step DOWNWARD is reset to $0$. There also seems to be a restriction on $r$, which may also be a function of $n$, but it seems more complicated.

The conditions on going "down" and "right" make sense -- they both amount to preventing a series of actions whose net effect is to go "down right" and violate the product order. And making it possible to go down only one step at a time, or right only one step at a time, also prevents skipping entries in a way which would violate transitivity. And clearly the only way to reset going "right" a bunch of times without leading to an effective "down right" move is to do an "down left" move of some sort to reset things, and similarly the only way to reset going "down" a bunch of times without leading to an effective "up left", "up", or "left" move is to do an "up right". But the exact number of ways it is possible to do so seems to depend in general on the previous history of the path in a somewhat complex manner.

$\endgroup$
3
  • 2
    $\begingroup$ It might be worthwhile to check in OEIS: e.g., count the number for $m=2$ and $n=1,2,3,4,5,6$ and then checking in OEIS. $\endgroup$ – D.W. Mar 8 '20 at 5:17
  • $\begingroup$ @D.W. I may have messed up, since the counting became more difficult, but with $M=5$ fixed, I found $1$ extension for $N=1$, $2$ extensions for $N=2$, $5$ for $N=3$, 14 for $N=4$, and $42$ for $N=5$. (Unsurprisingly I don't really want to calculate it for $N=6$.) There is some amount of recursion, most obviously if one choose $(2,1) < (1,2)$, then the remaining number of extensions/paths is the same as the total number for $2 \times (N-1)$ (since the entries from $(1,2)$ to the lower right are just relabeled versions of those of $2 \times (N-1)$). So, starting with $N=2$, it seems that there $\endgroup$ – hasManyStupidQuestions Mar 8 '20 at 16:57
  • $\begingroup$ are $a(N-1)+1$ paths, then $a(N-1)+3$ paths, then $a(N-1)+9$ paths, then $a(N-1)+28$ paths. The first sequence, $1,2,5,14,42$ might be the Catalan numbers, if for no other reason than they are known to show up everywhere, and there were only 90 results in OEIS. The second sequence, $1,3,9,28$ also registers only $74$ hits in OEIS, and the first one mentioned is also related to the Catalan numbers. And the Dyck path problems, since they are grid paths with a "no upper left" rule, would seem to be related to this problem, and are also related to Catalan numbers. Not sure if this helps for $M>2$. $\endgroup$ – hasManyStupidQuestions Mar 8 '20 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.