The train marshalling problem

NEW

Problem: Reconstructed statement: for a partition $S$ of $[n]=\{1,\dots,n\}$, let $K(S)$ be the least $k$ such that some concatenation of the parts of $S$, with arbitrary internal order in each part, is a subsequence of

Let $K(n,m)$ be the maximum of $K(S)$ over partitions of $[n]$ in which every part has size at least $m$. The conjecture asserts

Result: The conjecture is false.

Take $n=7,\ m=2$, and

All parts have size at least $2$. Here $d=\lfloor 7/2\rfloor=3$, so the conjectured upper bound is

But $K(S)=3$. Certainly $K(S)\le 3$, since

is a subsequence of $(1,2,\dots,7)^3$ with destination blocks contiguous.

Now suppose $K(S)\le2$. A word with distinct letters is a subsequence of $(1,\dots,7)^2$ iff it splits into two increasing runs. The split can cut at most one destination block.

No two whole blocks can lie in the same increasing run, since the intervals

overlap pairwise: for no ordered pair $X,Y$ do we have $\max X<\min Y$.

Thus exactly one block must be split, and it must be the middle block in the block order. If the order is $P,Y,Q$, with $Y=R\cup T$, where $R$ is before the split and $T$ after, then every element of $R$ must exceed $\max P$, and every element of $T$ must be below $\min Q$. Checking the possibilities:

• $Y=\{1,4,6\}$: if $P=\{2,5\}$, then $R\subseteq\{6\}$, so $4\in T$, but $4\not<3$; if $P=\{3,7\}$, no element of $Y$ exceeds $7$.
• $Y=\{2,5\}$: no element exceeds $6$ or $7$, impossible.
• $Y=\{3,7\}$: then $R=\{7\}$, $T=\{3\}$, but $3\not<2$ and $3\not<1$.

Contradiction. Hence $K(S)>2$, so $K(S)=3$, and therefore

disproving the conjectured inequality.

Citation: Definitions trace to Dahlhaus, Horak, Miller, and Ryan, “The train marshalling problem,” Discrete Applied Mathematics 103 (2000), 41–54. No published source is used for the counterexample above.