What is the length of the longest decreasing sequence in integer matrix?

Question

Given a finite $m \times n$ matrix $M$ with all distinct integers, we travel it following two simple rules:

• The travel can start from any cell, say, $M[i,j]$.
• At each cell $M[i,j]$, it computes the minimum $m$ of all its adjacent cells and itself, namely $$m = \min(M[i,j], M[i-1,j], M[i+1, j], M[i, j-1], M[i, j+1]),$$ and goes to the cell with the value $m$.
  Note that the travel is stuck if $m = M[i,j]$; it terminates in this case.

In this manner, each travel corresponds to a monotonically decreasing integer sequence. The question is:

What is the length of the longest decreasing sequence(s)?
In other words, I am seeking for matrices that contain such sequences as long as possible.

---

Note: Since it can be easily modeled as a graph problem, I use the graph-theory tag.

Answer 1

I will illustrate a $5x5$ matrix that gives such sequence of length $O(nm)$. The extension should be easy to see.

1  2  3  4  5
X  X  X  X  6
11 10 9  8  7
12 X  X  X  X
13 14 15 16 17

You should replace X with some large number (e.g., $nm+1$). If you start from the bottom right, the length of your sequence is at least $\frac{mn}{2}$.