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?

  • 2
    $\begingroup$ I think that this might be what you have in mind: arxiv.org/abs/0805.2860. In case it is, I am very interested in it myself... $\endgroup$ Mar 28, 2013 at 19:20
  • 2
    $\begingroup$ There are papers on "permutation arrays" by Eriksson and Linusson which might be useful; there is a paper by Billey and Vakil using this to solve Schubert problems. $\endgroup$ Mar 28, 2013 at 19:37
  • $\begingroup$ According to this philosophy, the number of $n \times n \times n$ permutation matrices should be $\sum_{|\lambda|=n} \# SYT(\lambda)^3$. This sequence is oeis.org/A130721 , but no combinatorial interpretations besides the tautological are listed. $\endgroup$ Mar 29, 2013 at 0:12
  • 2
    $\begingroup$ David, I think the standard tableaux version of the Stanley exercise mentioned above should be: let $M$ be the regular representation of $\mathcal S_n$, $f^\lambda$ the number of SYT of shape $\lambda$, and $M_\nu$ the irreducible $\mathcal S_n$-module of shape $\nu$. Then, as an $\mathcal S_n$-module, $M \otimes M \cong \bigoplus_{\lambda, \mu, \nu} f^\lambda f^\mu g_{\lambda \mu \nu} M_\nu$, so we should seek a bijection $$ \mathcal S_n \times \mathcal S_n \cong \bigsqcup_{\lambda, \mu, \nu} \text{SYT}(\lambda) \times \text{SYT}(\mu) \times \text{SYT}(\nu) \times [g_{\lambda \mu \nu}.$$ $\endgroup$ Mar 29, 2013 at 14:03
  • $\begingroup$ The recent paper arxiv.org/pdf/2009.00592.pdf by Amanov and Yeliussizov is relevant. $\endgroup$ Sep 13, 2020 at 23:27

2 Answers 2


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$.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.