Linear Extension of the $n\times n$ lattice

Question

I am looking at a particular integer sequence, the number of $n\times n$ Young Tableaus (see OEIS). In the comments at OEIS, Mitch Harris stated that the same sequence also defines the

Number of linear extensions of the $n\times n$ lattice.

When looking for some more explanation, I found quite some literature on Boolean Lattices and their linear extensions, but nothing on the $n\times n$ lattice. Not even a definition. Therefore:

1. What is the $n\times n$ lattice?
2. What is a linear extension of such a lattice?
3. Where can I find proof for the statement above?

Alternatively, I take any hints on literature on any of the three questions.

.

Answer 1

1. The $n \times n$ lattice just means the product poset of two chains: $[0,n] \times [0,n]=\{(i,j) | 0 \leq i,j \leq n\}$ where $(i,j) \leq (i',j')$ if and only if $i \leq i'$ and $j \leq j'$.
2. A linear extension of a poset $P$ with $m$ elements is just a bijection $f: P \to \{1,...,m\}$ such that $x \leq y$ in $P$ implies $f(x) \leq f(y)$.
3. If we identify the elements of $[0,n] \times [0,n]$ with the boxes of a square Young diagram, then the condition that $f$ is a linear extension is exactly the same as the condition that the tableau formed by putting the number $f(x)$ in the box corresponding to $x$ is a Young tableau.

This is a special case of a much more general phenomenon. The essential fact is that Young's lattice $Y$ (the set of Young diagrams ordered by inclusion) is the lattice of order ideals of $\mathbb{N} \times \mathbb{N}$. Therefore linear extensions of some ideal $I$ in $\mathbb{N} \times \mathbb{N}$ (in this case $I=[0,n] \times [0,n]$) correspond to maximal chains from $\emptyset$ to $I$ in $Y$. Such chains can naturally be identified with Young tableau by giving boxes the label of the first element of the chain which contains that box.

Answer 2

The $n\times n$ lattice is the set $X_n :=\{(i,j)\mid 1\leq i,j\leq n\}$, partially ordered by $(i,j)\leq (k,l)$ if $i\leq k$ and $j\leq l$.

A linear extension of any poset $P$ (of cardinality $N$) is a bijective function $f:P\to \{1,\dotsc, N\}$ such that, whenever $x\leq y$ in $P$, $f(x)\leq f(y)$ in the usual order on integers.

Now in the case of the $n\times n$ lattice, a linear extension $f:X_n\to \{1,\dotsc, n^2\}$ gives rise to $n\times n$ matrix $A_{ij} = f(i,j)$. This is a matrix whose rows and columns are strictly increasing, and such that each of the integers $1,\dotsc, n^2$ occurs exactly once.

This is a special case of a more general notion of a Young tableau, which can be viewed as a linear extension of the poset $P_\lambda$ associated to the integer partition $\lambda = (\lambda_1,\dotsc, \lambda_l)$. The poset $P_\lambda$ is the set $\{(i,j)\mid 1\leq i\leq l, 1\leq j \leq \lambda_i\}$, with the same order relation as that defined on $X_n$ earlier. In fact $X_n = P_{(n,\dotsc, n)}$ ($n$ appears $n$ times).

The number of such linear extension are given by the hook-length formula of Frame, Robinson, and Thrall, a celebrated result in combinatorics. A great reference is the book Enumerative Combinatorics, vol. 2, by Richard P. Stanley. It's also explained in my book Representation Theory: A Combinatorial Viewpoint.