The Hillman-Grassl correspondence#
This module implements weak reverse plane partitions and four correspondences on them: the Hillman-Grassl correspondence and its inverse, as well as the Sulzgruber correspondence and its inverse (the Pak correspondence).
Fix a partition \(\lambda\)
(see Partition()
).
We draw all partitions and tableaux in English notation.
A \(\lambda\)-array will mean a tableau of shape \(\lambda\) whose entries are nonnegative integers. (No conditions on the order of these entries are made. Note that \(0\) is allowed.)
A weak reverse plane partition of shape \(\lambda\) (short: \(\lambda\)-rpp) will mean a \(\lambda\)-array whose entries weakly increase along each row and weakly increase along each column. (The name “weak reverse plane partition” comes from Stanley in [EnumComb2] Section 7.22; other authors – such as Pak [Sulzgr2017], or Hillman and Grassl in [HilGra1976] – just call it a reverse plane partition.)
The Hillman-Grassl correspondence is a bijection from the
set of \(\lambda\)-arrays to the set of \(\lambda\)-rpps.
For its definition, see
hillman_grassl()
;
for its inverse, see
hillman_grassl_inverse()
.
The Sulzgruber correspondence \(\Phi_\lambda\) and the Pak
correspondence \(\xi_\lambda\) are two further mutually
inverse bijections between the set of
\(\lambda\)-arrays and the set of \(\lambda\)-rpps.
They appear (sometimes with different definitions, but
defining the same maps) in [Pak2002], [Hopkins2017] and
[Sulzgr2017]. For their definitions, see
sulzgruber_correspondence()
and
pak_correspondence()
.
EXAMPLES:
We construct a \(\lambda\)-rpp for \(\lambda = (3, 3, 1)\) (note that \(\lambda\) needs not be specified explicitly):
sage: p = WeakReversePlanePartition([[0, 1, 3], [2, 4, 4], [3]])
sage: p.parent()
Weak Reverse Plane Partitions
(This is the example in Section 7.22 of [EnumComb2].)
Next, we apply the inverse of the Hillman-Grassl correspondence to it:
sage: HGp = p.hillman_grassl_inverse(); HGp
[[1, 2, 0], [1, 0, 1], [1]]
sage: HGp.parent()
Tableaux
This is a \(\lambda\)-array, encoded as a tableau. We can recover our original \(\lambda\)-rpp from it using the Hillman-Grassl correspondence:
sage: HGp.hillman_grassl() == p
True
We can also apply the Pak correspondence to our rpp:
sage: Pp = p.pak_correspondence(); Pp
[[2, 0, 1], [0, 2, 0], [1]]
sage: Pp.parent()
Tableaux
This is undone by the Sulzgruber correspondence:
sage: Pp.sulzgruber_correspondence() == p
True
These four correspondences can also be accessed as standalone
functions (hillman_grassl_inverse()
, hillman_grassl()
,
pak_correspondence()
and sulzgruber_correspondence()
)
that transform lists of lists into lists of lists;
this may be more efficient. For example, the above computation
of HGp
can also be obtained as follows:
sage: from sage.combinat.hillman_grassl import hillman_grassl_inverse
sage: HGp_bare = hillman_grassl_inverse([[0, 1, 3], [2, 4, 4], [3]])
sage: HGp_bare
[[1, 2, 0], [1, 0, 1], [1]]
sage: isinstance(HGp_bare, list)
True
REFERENCES:
AUTHORS:
Darij Grinberg and Tom Roby (2018): Initial implementation
- class sage.combinat.hillman_grassl.WeakReversePlanePartition(parent, t)#
Bases:
Tableau
A weak reverse plane partition (short: rpp).
A weak reverse plane partition is a tableau with nonnegative entries that are weakly increasing in each row and weakly increasing in each column.
EXAMPLES:
sage: x = WeakReversePlanePartition([[0, 1, 1], [0, 1, 3], [1, 2, 2], [1, 2, 3], [2]]); x [[0, 1, 1], [0, 1, 3], [1, 2, 2], [1, 2, 3], [2]] sage: x.pp() 0 1 1 0 1 3 1 2 2 1 2 3 2 sage: x.shape() [3, 3, 3, 3, 1]
- conjugate()#
Return the conjugate of
self
.EXAMPLES:
sage: c = WeakReversePlanePartition([[1,1],[1,3],[2]]).conjugate(); c [[1, 1, 2], [1, 3]] sage: c.parent() Weak Reverse Plane Partitions
- hillman_grassl_inverse()#
Return the image of the \(\lambda\)-rpp
self
under the inverse of the Hillman-Grassl correspondence (as aTableau
).Fix a partition \(\lambda\) (see
Partition()
). We draw all partitions and tableaux in English notation.A \(\lambda\)-array will mean a tableau of shape \(\lambda\) whose entries are nonnegative integers. (No conditions on the order of these entries are made. Note that \(0\) is allowed.)
A weak reverse plane partition of shape \(\lambda\) (short: \(\lambda\)-rpp) will mean a \(\lambda\)-array whose entries weakly increase along each row and weakly increase along each column.
The inverse \(H^{-1}\) of the Hillman-Grassl correspondence (see (
hillman_grassl()
for the latter) sends a \(\lambda\)-rpp \(\pi\) to a \(\lambda\)-array \(H^{-1}(\pi)\) constructed recursively as follows:If all entries of \(\pi\) are \(0\), then \(H^{-1}(\pi) = \pi\).
Otherwise, let \(s\) be the index of the leftmost column of \(\pi\) containing a nonzero entry. Write the \(\lambda\)-array \(M\) as \((m_{i, j})\).
Define a sequence \(((i_1, j_1), (i_2, j_2), \ldots, (i_n, j_n))\) of boxes in the diagram of \(\lambda\) (actually a lattice path made of northward and eastward steps) as follows: Let \((i_1, j_1)\) be the bottommost box in the \(s\)-th column of \(\pi\). If \((i_k, j_k)\) is defined for some \(k \geq 1\), then \((i_{k+1}, j_{k+1})\) is constructed as follows: If \(q_{i_k - 1, j_k}\) is well-defined and equals \(q_{i_k, j_k}\), then we set \((i_{k+1}, j_{k+1}) = (i_k - 1, j_k)\). Otherwise, we set \((i_{k+1}, j_{k+1}) = (i_k, j_k + 1)\) if this is still a box of \(\lambda\). Otherwise, the sequence ends here.
Let \(\pi'\) be the \(\lambda\)-rpp obtained from \(\pi\) by subtracting \(1\) from the \((i_k, j_k)\)-th entry of \(\pi\) for each \(k \in \{1, 2, \ldots, n\}\).
Let \(N'\) be the image \(H^{-1}(\pi')\) (which is already constructed by recursion). Then, \(H^{-1}(\pi)\) is obtained from \(N'\) by adding \(1\) to the \((i_n, s)\)-th entry of \(N'\).
This construction appears in [HilGra1976] Section 6 (where \(\lambda\)-arrays are re-encoded as sequences of “hook number multiplicities”) and [EnumComb2] Section 7.22.
See also
hillman_grassl_inverse()
for the inverse of the Hillman-Grassl correspondence as a standalone function.hillman_grassl()
for the inverse map.EXAMPLES:
sage: a = WeakReversePlanePartition([[2, 2, 4], [2, 3, 4], [3, 5]]) sage: a.hillman_grassl_inverse() [[2, 1, 1], [0, 2, 0], [1, 1]] sage: b = WeakReversePlanePartition([[1, 1, 2, 2], [1, 1, 2, 2], [2, 2, 3, 3], [2, 2, 3, 3]]) sage: B = b.hillman_grassl_inverse(); B [[1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: b.parent(), B.parent() (Weak Reverse Plane Partitions, Tableaux)
Applying the inverse of the Hillman-Grassl correspondence to the transpose of a \(\lambda\)-rpp \(M\) yields the same result as applying it to \(M\) and then transposing the result ([Gans1981] Corollary 3.4):
sage: a = WeakReversePlanePartition([[1,3,5],[2,4]]) sage: aic = a.hillman_grassl_inverse().conjugate() sage: aic == a.conjugate().hillman_grassl_inverse() True
- pak_correspondence()#
Return the image of the \(\lambda\)-rpp
self
under the Pak correspondence (as aTableau
).See
hillman_grassl
.The Pak correspondence is the map \(\xi_\lambda\) from [Sulzgr2017] Section 7, and is the map \(\xi_\lambda\) from [Pak2002] Section 4. It is the inverse of the Sulzgruber correspondence (
sulzgruber_correspondence()
). The following description of the Pak correspondence follows [Hopkins2017] (which denotes it by \(\mathcal{RSK}^{-1}\)):Fix a partition \(\lambda\) (see
Partition()
). We draw all partitions and tableaux in English notation.A \(\lambda\)-array will mean a tableau of shape \(\lambda\) whose entries are nonnegative integers. (No conditions on the order of these entries are made. Note that \(0\) is allowed.)
A weak reverse plane partition of shape \(\lambda\) (short: \(\lambda\)-rpp) will mean a \(\lambda\)-array whose entries weakly increase along each row and weakly increase along each column.
We shall also use the following notation: If \((u, v)\) is a cell of \(\lambda\), and if \(\pi\) is a \(\lambda\)-rpp, then:
the lower bound of \(\pi\) at \((u, v)\) (denoted by \(\pi_{<(u, v)}\)) is defined to be \(\max \{ \pi_{u-1, v} , \pi_{u, v-1} \}\) (where \(\pi_{0, v}\) and \(\pi_{u, 0}\) are understood to mean \(0\)).
the upper bound of \(\pi\) at \((u, v)\) (denoted by \(\pi_{>(u, v)}\)) is defined to be \(\min \{ \pi_{u+1, v} , \pi_{u, v+1} \}\) (where \(\pi_{i, j}\) is understood to mean \(+ \infty\) if \((i, j)\) is not in \(\lambda\); thus, the upper bound at a corner cell is \(+ \infty\)).
toggling \(\pi\) at \((u, v)\) means replacing the entry \(\pi_{u, v}\) of \(\pi\) at \((u, v)\) by \(\pi_{<(u, v)} + \pi_{>(u, v)} - \pi_{u, v}\) (this is well-defined as long as \((u, v)\) is not a corner of \(\lambda\)).
Note that every \(\lambda\)-rpp \(\pi\) and every cell \((u, v)\) of \(\lambda\) satisfy \(\pi_{<(u, v)} \leq \pi_{u, v} \leq \pi_{>(u, v)}\). Note that toggling a \(\lambda\)-rpp (at a cell that is not a corner) always results in a \(\lambda\)-rpp. Also, toggling is an involution).
Note also that the lower bound of \(\pi\) at \((u, v)\) is defined (and finite) even when \((u, v)\) is not a cell of \(\lambda\), as long as both \((u-1, v)\) and \((u, v-1)\) are cells of \(\lambda\).
The Pak correspondence \(\Phi_\lambda\) sends a \(\lambda\)-array \(M = (m_{i, j})\) to a \(\lambda\)-rpp \(\Phi_\lambda(M)\). It is defined by recursion on \(\lambda\) (that is, we assume that \(\Phi_\mu\) is already defined for every partition \(\mu\) smaller than \(\lambda\)), and its definition proceeds as follows:
If \(\lambda = \varnothing\), then \(\Phi_\lambda\) is the obvious bijection sending the only \(\varnothing\)-array to the only \(\varnothing\)-rpp.
Pick any corner \(c = (i, j)\) of \(\lambda\), and let \(\mu\) be the result of removing this corner \(c\) from the partition \(\lambda\). (The exact choice of \(c\) is immaterial.)
Let \(M'\) be what remains of \(M\) when the corner cell \(c\) is removed.
Let \(\pi' = \Phi_\mu(M')\).
For each positive integer \(k\) such that \((i-k, j-k)\) is a cell of \(\lambda\), toggle \(\pi'\) at \((i-k, j-k)\). (All these togglings commute, so the order in which they are made is immaterial.)
Extend the \(\mu\)-rpp \(\pi'\) to a \(\lambda\)-rpp \(\pi\) by adding the cell \(c\) and writing the number \(m_{i, j} - \pi'_{<(i, j)}\) into this cell.
Set \(\Phi_\lambda(M) = \pi\).
See also
pak_correspondence()
for the Pak correspondence as a standalone function.sulzgruber_correspondence()
for the inverse map.EXAMPLES:
sage: a = WeakReversePlanePartition([[1, 2, 3], [1, 2, 3], [2, 4, 4]]) sage: A = a.pak_correspondence(); A [[1, 0, 2], [0, 2, 0], [1, 1, 0]] sage: a.parent(), A.parent() (Weak Reverse Plane Partitions, Tableaux)
Applying the Pak correspondence to the transpose of a \(\lambda\)-rpp \(M\) yields the same result as applying it to \(M\) and then transposing the result:
sage: a = WeakReversePlanePartition([[1,3,5],[2,4]]) sage: acc = a.pak_correspondence().conjugate() sage: acc == a.conjugate().pak_correspondence() True
- class sage.combinat.hillman_grassl.WeakReversePlanePartitions#
Bases:
Tableaux
The set of all weak reverse plane partitions.
- Element#
alias of
WeakReversePlanePartition
- an_element()#
Returns a particular element of the class.
- sage.combinat.hillman_grassl.hillman_grassl(M)#
Return the image of the \(\lambda\)-array
M
under the Hillman-Grassl correspondence.The Hillman-Grassl correspondence is a bijection between the tableaux with nonnegative entries (otherwise arbitrary) and the weak reverse plane partitions with nonnegative entries. This bijection preserves the shape of the tableau. See
hillman_grassl
.See
hillman_grassl()
for a description of this map.See also
EXAMPLES:
sage: from sage.combinat.hillman_grassl import hillman_grassl sage: hillman_grassl([[2, 1, 1], [0, 2, 0], [1, 1]]) [[2, 2, 4], [2, 3, 4], [3, 5]] sage: hillman_grassl([[1, 2, 0], [1, 0, 1], [1]]) [[0, 1, 3], [2, 4, 4], [3]] sage: hillman_grassl([]) [] sage: hillman_grassl([[3, 1, 2]]) [[3, 4, 6]] sage: hillman_grassl([[2, 2, 0], [1, 1, 1], [1]]) [[1, 2, 4], [3, 5, 5], [4]] sage: hillman_grassl([[1, 1, 1, 1]]*3) [[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6]]
- sage.combinat.hillman_grassl.hillman_grassl_inverse(M)#
Return the image of the \(\lambda\)-rpp
M
under the inverse of the Hillman-Grassl correspondence.See
hillman_grassl
.See
hillman_grassl_inverse()
for a description of this map.See also
EXAMPLES:
sage: from sage.combinat.hillman_grassl import hillman_grassl_inverse sage: hillman_grassl_inverse([[2, 2, 4], [2, 3, 4], [3, 5]]) [[2, 1, 1], [0, 2, 0], [1, 1]] sage: hillman_grassl_inverse([[0, 1, 3], [2, 4, 4], [3]]) [[1, 2, 0], [1, 0, 1], [1]]
Applying the inverse of the Hillman-Grassl correspondence to the transpose of a \(\lambda\)-rpp \(M\) yields the same result as applying it to \(M\) and then transposing the result ([Gans1981] Corollary 3.4):
sage: hillman_grassl_inverse([[1,3,5],[2,4]]) [[1, 2, 2], [1, 1]] sage: hillman_grassl_inverse([[1,2],[3,4],[5]]) [[1, 1], [2, 1], [2]] sage: hillman_grassl_inverse([[1, 2, 3], [1, 2, 3], [2, 4, 4]]) [[1, 2, 0], [0, 1, 1], [1, 0, 1]] sage: hillman_grassl_inverse([[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6]]) [[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]
- sage.combinat.hillman_grassl.pak_correspondence(M, copy=True)#
Return the image of a \(\lambda\)-rpp
M
under the Pak correspondence.The Pak correspondence is the map \(\xi_\lambda\) from [Sulzgr2017] Section 7, and is the map \(\xi_\lambda\) from [Pak2002] Section 4. It is the inverse of the Sulzgruber correspondence (
sulzgruber_correspondence()
).See
pak_correspondence()
for a description of this map.INPUT:
copy
(default:True
) – boolean; if set toFalse
, the algorithm will mutate the input (but be more efficient)
EXAMPLES:
sage: from sage.combinat.hillman_grassl import pak_correspondence sage: pak_correspondence([[1, 2, 3], [1, 2, 3], [2, 4, 4]]) [[1, 0, 2], [0, 2, 0], [1, 1, 0]] sage: pak_correspondence([[1, 1, 4], [2, 3, 4], [4, 4, 4]]) [[1, 1, 2], [0, 1, 0], [3, 0, 0]] sage: pak_correspondence([[0, 2, 3], [1, 3, 3], [2, 4]]) [[1, 0, 2], [0, 2, 0], [1, 1]] sage: pak_correspondence([[1, 2, 4], [1, 3], [3]]) [[0, 2, 2], [1, 1], [2]] sage: pak_correspondence([[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6]]) [[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]
The Pak correspondence can actually be extended (by the same definition) to “rpps” of nonnegative reals rather than nonnegative integers. This implementation supports this:
sage: pak_correspondence([[0, 1, 3/2], [1/2, 3/2, 3/2], [1, 2]]) [[1/2, 0, 1], [0, 1, 0], [1/2, 1/2]]
- sage.combinat.hillman_grassl.sulzgruber_correspondence(M)#
Return the image of a \(\lambda\)-array
M
under the Sulzgruber correspondence.The Sulzgruber correspondence is the map \(\Phi_\lambda\) from [Sulzgr2017] Section 7, and is the map \(\xi_\lambda^{-1}\) from [Pak2002] Section 5. It is denoted by \(\mathcal{RSK}\) in [Hopkins2017]. It is the inverse of the Pak correspondence (
pak_correspondence()
).See
sulzgruber_correspondence()
for a description of this map.EXAMPLES:
sage: from sage.combinat.hillman_grassl import sulzgruber_correspondence sage: sulzgruber_correspondence([[1, 0, 2], [0, 2, 0], [1, 1, 0]]) [[1, 2, 3], [1, 2, 3], [2, 4, 4]] sage: sulzgruber_correspondence([[1, 1, 2], [0, 1, 0], [3, 0, 0]]) [[1, 1, 4], [2, 3, 4], [4, 4, 4]] sage: sulzgruber_correspondence([[1, 0, 2], [0, 2, 0], [1, 1]]) [[0, 2, 3], [1, 3, 3], [2, 4]] sage: sulzgruber_correspondence([[0, 2, 2], [1, 1], [2]]) [[1, 2, 4], [1, 3], [3]] sage: sulzgruber_correspondence([[1, 1, 1, 1]]*3) [[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6]]
The Sulzgruber correspondence can actually be extended (by the same definition) to arrays of nonnegative reals rather than nonnegative integers. This implementation supports this:
sage: sulzgruber_correspondence([[1/2, 0, 1], [0, 1, 0], [1/2, 1/2]]) [[0, 1, 3/2], [1/2, 3/2, 3/2], [1, 2]]
- sage.combinat.hillman_grassl.transpose(M)#
Return the transpose of a \(\lambda\)-array.
The transpose of a \(\lambda\)-array \((m_{i, j})\) is the \(\lambda^t\)-array \((m_{j, i})\) (where \(\lambda^t\) is the conjugate of the partition \(\lambda\)).
EXAMPLES:
sage: from sage.combinat.hillman_grassl import transpose sage: transpose([[1, 2, 3], [4, 5]]) [[1, 4], [2, 5], [3]] sage: transpose([[5, 0, 3], [4, 1, 0], [7]]) [[5, 4, 7], [0, 1], [3, 0]]