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
-
sage.combinat.hillman_grassl.
WeakReversePlanePartition
¶ 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]
-
sage.combinat.hillman_grassl.
WeakReversePlanePartitions
¶ The set of all weak reverse plane partitions.
-
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]]