Bound on number of nxn grids with lexicographical ordering / poset structure

Question

Given $n\in\mathbb{N}$, consider the numbers $\{1,\ldots,n^2\}$ and a permutation $\pi\in S_{n^2}$. It induces pairs $(1,\pi(1))$, $\ldots$, $(n^2,\pi(n^2))$.

Consider an $n\times n$ grid. How many possibilities are there to place the pairs in the grid such that each row grows from left to right in the first value of the pair, while each column grows from top to bottom in the second value?

e.g. $n=3$, some $\pi\in S_9$, a valid placement would be:

$\begin{align*} (1,2) && (2,1) && (3,3)\\ (4,4) && (5,5) && (9,6)\\ (6,7) && (7,8) && (8,9) \end{align*}$

For the the $\pi$, the following placement is not valid as the lower left $(8,9)$ has a larger first-coordinate (8) than the lower middle $(6,7)$ has (6).

$\begin{align*} (1,2) && (2,1) && (3,3)\\ (4,4) && (5,5) && (9,6)\\ (8,9) && (6,7) && (7,8) \end{align*}$

It seeems to me that it is somewhat hard to find an exact value for the number of valid placements for a given permutation $\pi$. Therefore, a hopefully easier, less accurate question: Is the above number always smaller or equal than the number for the specific permutation $\pi=id$?

In case of $\pi=id$, the number of valid placements is given by this sequence, which denotes the number of Young Tableaus of shape $(n,\ldots,n)$ or the number of linear extensions of the $n\times n$ lattice (see this question).

Answer 1

Let $(P,\le_P)$ and $(Q,\le_Q)$ be posets, although usually we will just refer to "$P$" and "$Q$". One can define a partial ordering $\le$ on the direct product $P\times Q$ as follows: $(p,q)\le(p',q')$ if $p\le_P p'$ and $q\le_Q q'$.

A function $f$ from $P$ to $Q$ is order-preserving if for all $p,p'\in P$, $p\le_P p'$ implies $f(p)\le_Q f(p')$.

You are considering certain subsets of $n^2$ points in $\mathbb N\times\mathbb N$ and regarding them as subposets.

If $\bf n$ is the $n$-element totally ordered set, you are interested in counting the number of bijective order-preserving maps from $\bf n\times\bf n$ onto one of the aforementioned subposets of $\mathbb N\times\mathbb N$.

The subset obtained from $\pi=id$ is a totally ordered set order-isomorphic to $\bf{n^2}$.

For any other $\pi$, this poset $Q_\pi$ will not be a totally ordered set, since there will be $a,b,c,d\in\mathbb N$ such that $1\le a<b\le n^2$ and $1\le d < c\le n^2$ but your poset has the pairs $(a,c)$ and $(b,d)$ and $(a,c)\nleq(b,d)$ and $(b,d)\nleq (a,c)$.

Any poset $(P,\le_P)$ has a linear extension (Szilprajn's Theorem): there is a totally ordered set $(L,\le_L)$ and an order-preserving bijection from $P$ onto $L$.

Fix such a map $\lambda$ from $Q_\pi$ onto such an $L$, which is order-isomorphic to ${\bf n^2}$, or $Q_{id}$.

Now any order-preserving bijection $b$ from $\bf n\times\bf n$ onto $Q_\pi$ can be composed with $\lambda$ and we still get an order-preserving bijection onto $Q_{id}$. This map $b\mapsto \lambda\circ b$ is one-to-one since $\lambda$ has an inverse (as a map of sets).

It's 6:32 a.m., but this looks right. Is it?

Answer 2

We have indeed found a proof based on an injection of the set of valid placements into the set of valid placements of the identity permutation. Find details in Theorem 9 of Version 4 of this ArXiv paper: https://arxiv.org/pdf/1710.03435.pdf.