3D generalizations of permutations, RSK correspondence, contingency tables, etc.

Question

I want to gather facts and questions related to 3D generalizations of permutations, RSK correspondence, contingency tables, etc. One reason I am interested in this is because it is potentially related to Kronecker coefficients. See for example the introduction to my paper Kronecker Coefficients for One Hook Shape (the third paragraph below explains the connection between this intro and 3D permutation matrices). Also (thanks to Alex Yong for pointing this out; this is exercise $7.78f$ in Stanley EC2)

$$ \prod_{i,j,k}\frac{1}{1-x_{i}y_{j}z_{k}}=\sum_{\lambda,\mu,\nu}g_{\lambda\mu\nu}s_{\lambda}(\mathbf{x})s_{\mu}(\mathbf{y})s_{\nu}(\mathbf{z}), $$ where $g_{\lambda\mu\nu}$ denotes the Kronecker coefficient. This suggests that we should look for a 3D generalization of the RSK correspondence that takes as input a 3D matrix with nonnegative integer entries and outputs three semistandard Young tableaux of shapes $\lambda,$ $\mu$ and $\nu$, and some object that is one of $g_{\lambda\mu\nu}$ many objects which give a combinatorial formula for this Kronecker coefficient.

Let us fix some notation for higher dimensional partitions and permutation matrices. A d-dimensional partition of $n$ is defined to be a map from $\mathbb Z^d_{>0}$ to $\mathbb Z_{\ge 0}$ such that it is weakly decreasing along all directions and the sum of all its entries add to $n$. With this convention, an ordinary partition of $n$ is a 1-dimensional partition and a plane partition is a 2-dimensional partition. I often like to think of ordinary partitions as 2-dimensional objects, so to achieve this without changing any established definitions, let us define a d-dimensional diagram to be a lower order ideal in the poset $\mathbb Z^d_{>0}$. Then $d$-dimensional diagrams can be identified with $(d-1)$-dimensional partitions.

There are at least two possible definitions of a 3D-permutation matrix. We can require that in every line, there is exactly one 1 and the rest 0's. This is the same as a Latin square. We can also require that in every plane, there is exactly one 1 and the rest 0's. With this latter definition, 3D-permutation matrices are in bijection with pairs of permutations: if $(\sigma,\pi)$ $\in$ $\mathcal S_{n}$ $\times\mathcal{{S}}_{n}$, then the $n\times n \times n$ 3D-matrix with a 1 in positions $(i, \sigma_i, \pi_i)$, $i \in [n]$ and 0's elsewhere is a 3D-permutation matrix. Also, given such a 3D permutation matrix, we can take sums along lines in three possible directions to obtain three permutation matrices; one of these permutation matrices is the product of the other two (perhaps with some inverses). Pairs of permutations and their products are possibly related to Kronecker coefficients, as discussed in the introduction to my paper mentioned above.

Here are some projects related to higher dimensional generalizations related to partitions and tableaux. I am hoping that people will add to this list and provide links to papers that investigate related things. Any connections between these different projects would also be interesting to know about (speculative answers welcome).

1. Study the longest increasing subsequence problem for pairs of permutations. Specifically, let $\mathcal S_n\times\mathcal S_n$ denote the set of pairs of permutations. For $(\sigma,\pi)\in\mathcal S_n\times\mathcal S_n$ let $pos(\sigma,\pi)$ denote the poset on $[n]$ in which $i$ is less than $j$ if and only if $i$ $< j$ for the usual order on $[n]$ and $\sigma(i)<\sigma(j)$ and $\pi(i)<\pi(j)$. And let $sh(\sigma,\pi)$ denote the Greene invariant of the poset $pos(\sigma,\pi)$. Thus the length of the first part of shape $sh(\sigma,\pi)$ is the length of the longest chain in this poset (we refer to chains in this poset as increasing subsequences of $(\sigma,\pi)$). More generally, it is possible to associate a triple of recording tableaux to $(\sigma,\pi)\in\mathcal S_n\times\mathcal S_n$. One can then study the statistics of the longest increasing subsequence--or the finer statistics of $sh(\sigma,\pi)$ or this triple of recording tableaux--over all pairs of permutations. I did some Monte Carlo simulations and found that the expected length of the longest increasing subsequence grows significantly faster than $n^{\frac{1}{3}}$ and a little slower than $n^{\frac{1}{2}}$. To compare, the expected length of the longest increasing subsequence of a permutation is known to be $2n^{\frac{1}{2}}$.

2. Counting 3D contingency tables: For a nonnegative integer matrix, the row sums and column sums give two compositions of the same number $n$. It is well known that the number of matrices with row sums $\alpha$ and column sums $\beta$ is equal to $\langle h_{n},h_{\alpha} * h_{\beta}\rangle$, where $*$ denotes the internal product of symmetric functions and $n = |\alpha| = |\beta|$. A nonnegative integer 3D-matrix can be sliced into planes in three directions. For each direction, taking the sum of all entries in each plane yields a composition. One can show that the number of nonnegative integer 3D matrices such that the planar slice sums are given by $\alpha,$ $\beta$ and $\gamma$ is equal to $\langle h_{n},h_{\alpha}* h_{\beta}*h_{\gamma}\rangle$, where $n = |\alpha| = |\beta| = |\gamma|$.

3. Counting 3-dimensional partitions (=4-dimensional diagrams). These are also called solid partitions and this problem is known to be difficult. See Counting Solid Partitions. If anyone knows of recent work on this problem that is not mentioned in the link, please let us know.

4. Counting $d$-dimensional standard Young tableaux. Define a $d$-SYT to be a linear ordering of a $d$-dimensional diagram. How many $d$-SYT are there of a given shape?

Answer 1

As regard to point 1, I have run some Monte Carlo for $(\sigma, \tau)\in \mathcal{S}_n \times \mathcal{S}_n$ for $n \leq 10^5$ and tried to measure the exponent $\xi$ defined by $LISS(\sigma, \tau) \sim n^\xi $. A slow crossover behavior is observed: If one stops by $n \sim 10^3$, one would get $\xi \sim 0.39$; But when pushing to $n \sim 10^5$, $\xi$ goes down to $0.345(5)$, quite close to the intuitive guess $1/3$.

Answer 2

For Problem 1, I believe you can just apply Ergodic Subadditivity (just like one does for Hammersly's proof of LIS) to show there exist some positive constant $c$ such that as $N\to \infty$, choosing random $\pi,\tau \in S_N$, whp $LISS(\pi,\tau) = (c+o(1))N^{1/3}$. Let $LISS(N)$ be the random variable that chooses $\pi,\tau \in S_N$ at random and returns $LISS(\pi,\tau)$.

Indeed, consider a Poisson process on $(0,\infty)^3$ with parameter one. Intuitively one axis represents the order of $[n]$, the next represents the order of $\pi$, and the last represents the order of $\tau$. For natural numbers $n<m$ we define $X(n,m)$ to be the cardinality of the longest increasing sequence of points from our process within $(n,m]^3$.

It is the case that $X(0,m) \ge X(0,n)+X(n,m)$ for all naturals $n<m$. Thus, by ergodic subadditivity, applied to $-X(\cdot,\cdot)$ and the ergodic shift of translation, we have almost surely $\lim_{n\to \infty} \frac{X(0,n)}{n} = Y$ for some constant $Y \in (-\infty,\infty]$.

It is not hard to see that conditioned on $(0,m]^3$ having $N$ points, that the distribution of $X(0,m)$ will be $LISS(N)$. As $(0,m]^3$ will almost surely have $\approx m^3$ points, we get that almost surely $$LISS(N) \approx (Y+o(1))N^{1/3}.$$Lastly, one can see $Y$ is positive and finite. Positivity is trivial, because $X(\cdot,\cdot)$ is always non-negative and is additive. Finiteness follows from considering first moments, such details can be found in Section 0.5 of https://www.stat.berkeley.edu/~aldous/Research/OP/substructures_posets.pdf.