  Let $(X_n)_{n \ge 0}$ be an irreducible, aperiodic, homogeneous Markov chain,
with state space an ordered finite alphabet of size $m$. Using combinatorial
constructions and weak invariance principles, we obtain the limiting shape of
the associated Young tableau as a multidimensional Brownian functional. Since
the length of the top row of the Young tableau is also the length of the
longest (weakly) increasing subsequence of $(X_k)_{1\le k \le n}$, the
corresponding limiting law follows. We relate our results to a conjecture of
Kuperberg by showing that, under a cyclic condition, a spectral
characterization of the Markov transition matrix delineates precisely when the
limiting shape is the spectrum of the traceless GUE. For $m=3$, all cyclic
Markov chains have such a limiting shape, a fact previously known for $m=2$.
However, this is no longer true for $m \ge 4$.
