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).
-
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}}$. -
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|$. -
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.
-
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?
Best Answer
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$.