Let $N$, $M$ and $K$ be natural numbers. Consider the directed graph with $N\times M$ vertices $V = \{(i, j) \mid i = 1 \ldots N, j = 1 \ldots M\}$ and edges $E \subset V^2$ with the following properties:
- $((i, j), (i, j + 1)) \in E$ for all $1 \leq i \leq N, 1 \leq j < M$;
- $((i, j), (k, j + 1)) \notin E$ for all $1 \leq i < k \leq N, 1 \leq j < M$;
- If for some $v \in V$ there are $K$ vertices $u_1, \ldots, u_K$, such that $(u_s, u_{s+1})\in E$ for all $1 \leq s < K$ and $v < u_1$, than $(v, u_s) \in E$ for some $s \in \{1 \ldots K\}$;
where $(i, j) < (i', j') \iff i < i'$ or $i = i'$ and $j < j'$.
I wonder, if for some $K$ there are such graphs for arbitrarily large $N$ and $M$.
It's obvious, that for $K = 1$ there can be no such graph even for $N = 2$. I've also proved the boundness for $K = 2, 3$ and $4$, but these arguments are like brute forcing and are not generalizable.
Are there any methods, that could be helpful for this task? Any ideas are welcome