Partition tuples

A PartitionTuple is a tuple of partitions. That is, an ordered \(k\)-tuple of partitions \(\mu=(\mu^{(1)},\mu^{(2)},...,\mu^{(k)})\). If

\[n = \lvert \mu \rvert = \lvert \mu^{(1)} \rvert + \lvert \mu^{(2)} \rvert + \cdots + \lvert \mu^{(k)} \rvert\]

then we say that \(\mu\) is a \(k\)-partition of \(n\).

In representation theory partition tuples arise as the natural indexing set for the ordinary irreducible representations of:

  • the wreath products of cyclic groups with symmetric groups,
  • the Ariki-Koike algebras, or the cyclotomic Hecke algebras of the complex reflection groups of type \(G(r,1,n)\),
  • the degenerate cyclotomic Hecke algebras of type \(G(r,1,n)\).

When these algebras are not semisimple, partition tuples index an important class of modules for the algebras, which are generalisations of the Specht modules of the symmetric groups.

Tuples of partitions also index the standard basis of the higher level combinatorial Fock spaces. As a consequence, the combinatorics of partition tuples encapsulates the canonical bases of crystal graphs for the irreducible integrable highest weight modules of the (quantized) affine special linear groups and the (quantized) affine general linear groups. By the categorification theorems of Ariki, Varagnolo-Vasserot, Stroppel-Webster and others, in characteristic zero the degenerate and non-degenerate cyclotomic Hecke algebras, via their Khovanov-Lauda-Rouquier grading, categorify the canonical bases of the quantum affine special and general linear groups.

Partitions are naturally in bijection with 1-tuples of partitions. Most of the combinatorial operations defined on partitions extend to partition tuples in a meaningful way. For example, the semisimple branching rules for the Specht modules are described by adding and removing cells from partition tuples and the modular branching rules correspond to adding and removing good and cogood nodes, which is the underlying combinatorics for the associated crystal graphs.

A PartitionTuple belongs to PartitionTuples and its derived classes. PartitionTuples is the parent class for all partitions tuples. Four different classes of tuples of partitions are currently supported:

  • PartitionTuples(level=k,size=n) are \(k\)-tuple of partitions of \(n\).
  • PartitionTuples(level=k) are \(k\)-tuple of partitions.
  • PartitionTuples(size=n) are tuples of partitions of \(n\).
  • PartitionTuples() are tuples of partitions.

Note

As with Partitions, in sage the cells, or nodes, of partition tuples are 0-based. For example, the (lexicographically) first cell in any non-empty partition tuple is \([0,0,0]\).

EXAMPLES:

sage: PartitionTuple([[2,2],[1,1],[2]]).cells()
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 1, 0), (2, 0, 0), (2, 0, 1)]

Note

Many PartitionTuple methods take the individual coordinates \((k,r,c)\) as their arguments, here \(k\) is the component, \(r\) is the row index and \(c\) is the column index. If your coordinates are in the form (k,r,c) then use Python’s *-operator.

EXAMPLES:

sage: mu=PartitionTuple([[1,1],[2],[2,1]])
sage: [ mu.arm_length(*c) for c in mu.cells()]
[0, 0, 1, 0, 1, 0, 0]

Warning

In sage, if mu is a partition tuple then mu[k] most naturally refers to the \(k\)-th component of mu, so we use the convention of the \((k,r,c)\)-th cell in a partition tuple refers to the cell in component \(k\), row \(r\), and column \(c\). In the literature, the cells of a partition tuple are usually written in the form \((r,c,k)\), where \(r\) is the row index, \(c\) is the column index, and \(k\) is the component index.

REFERENCES:

AUTHORS:

  • Andrew Mathas (2012-06-01): Initial classes.

EXAMPLES:

First is a finite enumerated set and the remaining classes are infinite enumerated sets:

sage: PartitionTuples().an_element()
([1, 1, 1, 1], [2, 1, 1], [3, 1], [4])
sage: PartitionTuples(4).an_element()
([], [1], [2], [3])
sage: PartitionTuples(size=5).an_element()
([1], [1], [1], [1], [1])
sage: PartitionTuples(4,5).an_element()
([1], [], [], [4])
sage: PartitionTuples(3,2)[:]
[([2], [], []),
 ([1, 1], [], []),
 ([1], [1], []),
 ([1], [], [1]),
 ([], [2], []),
 ([], [1, 1], []),
 ([], [1], [1]),
 ([], [], [2]),
 ([], [], [1, 1])]
sage: PartitionTuples(2,3).list()
[([3], []),
 ([2, 1], []),
 ([1, 1, 1], []),
 ([2], [1]),
 ([1, 1], [1]),
 ([1], [2]),
 ([1], [1, 1]),
 ([], [3]),
 ([], [2, 1]),
 ([], [1, 1, 1])]

One tuples of partitions are naturally in bijection with partitions and, as far as possible, partition tuples attempts to identify one tuples with partitions:

sage: Partition([4,3]) == PartitionTuple([[4,3]])
True
sage: Partition([4,3]) == PartitionTuple([4,3])
True
sage: PartitionTuple([4,3])
[4, 3]
sage: Partition([4,3]) in PartitionTuples()
True

Partition tuples come equipped with many of the corresponding methods for partitions. For example, it is possible to add and remove cells, to conjugate partition tuples, to work with their diagrams, compare partition tuples in dominance and so:

sage: PartitionTuple([[4,1],[],[2,2,1],[3]]).pp()
   ****   -   **   ***
   *          **
              *
sage: PartitionTuple([[4,1],[],[2,2,1],[3]]).conjugate()
([1, 1, 1], [3, 2], [], [2, 1, 1, 1])
sage: PartitionTuple([[4,1],[],[2,2,1],[3]]).conjugate().pp()
   *   ***   -   **
   *   **        *
   *             *
                 *
sage: lam=PartitionTuples(3)([[3,2],[],[1,1,1,1]]); lam
([3, 2], [], [1, 1, 1, 1])
sage: lam.level()
3
sage: lam.size()
9
sage: lam.category()
Category of elements of Partition tuples of level 3
sage: lam.parent()
Partition tuples of level 3
sage: lam[0]
[3, 2]
sage: lam[1]
[]
sage: lam[2]
[1, 1, 1, 1]
sage: lam.pp()
   ***   -   *
   **        *
             *
             *
sage: lam.removable_cells()
[(0, 0, 2), (0, 1, 1), (2, 3, 0)]
sage: lam.down_list()
[([2, 2], [], [1, 1, 1, 1]),
 ([3, 1], [], [1, 1, 1, 1]),
 ([3, 2], [], [1, 1, 1])]
sage: lam.addable_cells()
[(0, 0, 3), (0, 1, 2), (0, 2, 0), (1, 0, 0), (2, 0, 1), (2, 4, 0)]
sage: lam.up_list()
[([4, 2], [], [1, 1, 1, 1]),
 ([3, 3], [], [1, 1, 1, 1]),
 ([3, 2, 1], [], [1, 1, 1, 1]),
 ([3, 2], [1], [1, 1, 1, 1]),
 ([3, 2], [], [2, 1, 1, 1]),
 ([3, 2], [], [1, 1, 1, 1, 1])]
sage: lam.conjugate()
([4], [], [2, 2, 1])
sage: lam.dominates( PartitionTuple([[3],[1],[2,2,1]]) )
False
sage: lam.dominates( PartitionTuple([[3],[2],[1,1,1]]))
True

Every partition tuple behaves every much like a tuple of partitions:

sage: mu=PartitionTuple([[4,1],[],[2,2,1],[3]])
sage: [ nu for nu in mu ]
[[4, 1], [], [2, 2, 1], [3]]
sage: Set([ type(nu) for nu in mu ])
{<class 'sage.combinat.partition.Partitions_all_with_category.element_class'>}
sage: mu[2][2]
1
sage: mu[3]
[3]
sage: mu.components()
[[4, 1], [], [2, 2, 1], [3]]
sage: mu.components() == [ nu for nu in mu ]
True
sage: mu[0]
[4, 1]
sage: mu[1]
[]
sage: mu[2]
[2, 2, 1]
sage: mu[2][0]
2
sage: mu[2][1]
2
sage: mu.level()
4
sage: len(mu)
4
sage: mu.cells()
[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 1, 0), (2, 0, 0), (2, 0, 1), (2, 1, 0), (2, 1, 1), (2, 2, 0), (3, 0, 0), (3, 0, 1), (3, 0, 2)]
sage: mu.addable_cells()
[(0, 0, 4), (0, 1, 1), (0, 2, 0), (1, 0, 0), (2, 0, 2), (2, 2, 1), (2, 3, 0), (3, 0, 3), (3, 1, 0)]
sage: mu.removable_cells()
[(0, 0, 3), (0, 1, 0), (2, 1, 1), (2, 2, 0), (3, 0, 2)]

Attached to a partition tuple is the corresponding Young, or parabolic, subgroup:

sage: mu.young_subgroup()
Permutation Group with generators [(), (12,13), (11,12), (8,9), (6,7), (3,4), (2,3), (1,2)]
sage: mu.young_subgroup_generators()
[1, 2, 3, 6, 8, 11, 12]
sage.combinat.partition_tuple.PartitionTuple

A tuple of Partition.

A tuple of partition comes equipped with many of methods available to partitions. The level of the PartitionTuple is the length of the tuple.

This is an ordered \(k\)-tuple of partitions \(\mu=(\mu^{(1)},\mu^{(2)},...,\mu^{(k)})\). If

\[n = \lvert \mu \rvert = \lvert \mu^{(1)} \rvert + \lvert \mu^{(2)} \rvert + \cdots + \lvert \mu^{(k)} \rvert\]

then \(\mu\) is a \(k\)-partition of \(n\).

In representation theory PartitionTuples arise as the natural indexing set for the ordinary irreducible representations of:

  • the wreath products of cyclic groups with symmetric groups
  • the Ariki-Koike algebras, or the cyclotomic Hecke algebras of the complex reflection groups of type \(G(r,1,n)\)
  • the degenerate cyclotomic Hecke algebras of type \(G(r,1,n)\)

When these algebras are not semisimple, partition tuples index an important class of modules for the algebras which are generalisations of the Specht modules of the symmetric groups.

Tuples of partitions also index the standard basis of the higher level combinatorial Fock spaces. As a consequence, the combinatorics of partition tuples encapsulates the canonical bases of crystal graphs for the irreducible integrable highest weight modules of the (quantized) affine special linear groups and the (quantized) affine general linear groups. By the categorification theorems of Ariki, Varagnolo-Vasserot, Stroppel-Webster and others, in characteristic zero the degenerate and non-degenerate cyclotomic Hecke algebras, via their Khovanov-Lauda-Rouquier grading, categorify the canonical bases of the quantum affine special and general linear groups.

Partitions are naturally in bijection with 1-tuples of partitions. Most of the combinatorial operations defined on partitions extend to PartitionTuples in a meaningful way. For example, the semisimple branching rules for the Specht modules are described by adding and removing cells from partition tuples and the modular branching rules correspond to adding and removing good and cogood nodes, which is the underlying combinatorics for the associated crystal graphs.

Warning

In the literature, the cells of a partition tuple are usually written in the form \((r,c,k)\), where \(r\) is the row index, \(c\) is the column index, and \(k\) is the component index. In sage, if mu is a partition tuple then mu[k] most naturally refers to the \(k\)-th component of mu, so we use the convention of the \((k,r,c)\)-th cell in a partition tuple refers to the cell in component \(k\), row \(r\), and column \(c\).

INPUT:

Anything which can reasonably be interpreted as a tuple of partitions. That is, a list or tuple of partitions or valid input to Partition.

EXAMPLES:

sage: mu=PartitionTuple( [[3,2],[2,1],[],[1,1,1,1]] ); mu
([3, 2], [2, 1], [], [1, 1, 1, 1])
sage: nu=PartitionTuple( ([3,2],[2,1],[],[1,1,1,1]) ); nu
([3, 2], [2, 1], [], [1, 1, 1, 1])
sage: mu == nu
True
sage: mu is nu
False
sage: mu in PartitionTuples()
True
sage: mu.parent()
Partition tuples

sage: lam=PartitionTuples(3)([[3,2],[],[1,1,1,1]]); lam
([3, 2], [], [1, 1, 1, 1])
sage: lam.level()
3
sage: lam.size()
9
sage: lam.category()
Category of elements of Partition tuples of level 3
sage: lam.parent()
Partition tuples of level 3
sage: lam[0]
[3, 2]
sage: lam[1]
[]
sage: lam[2]
[1, 1, 1, 1]
sage: lam.pp()
   ***   -   *
   **        *
             *
             *
sage: lam.removable_cells()
[(0, 0, 2), (0, 1, 1), (2, 3, 0)]
sage: lam.down_list()
[([2, 2], [], [1, 1, 1, 1]), ([3, 1], [], [1, 1, 1, 1]), ([3, 2], [], [1, 1, 1])]
sage: lam.addable_cells()
[(0, 0, 3), (0, 1, 2), (0, 2, 0), (1, 0, 0), (2, 0, 1), (2, 4, 0)]
sage: lam.up_list()
[([4, 2], [], [1, 1, 1, 1]), ([3, 3], [], [1, 1, 1, 1]), ([3, 2, 1], [], [1, 1, 1, 1]), ([3, 2], [1], [1, 1, 1, 1]), ([3, 2], [], [2, 1, 1, 1]), ([3, 2], [], [1, 1, 1, 1, 1])]
sage: lam.conjugate()
([4], [], [2, 2, 1])
sage: lam.dominates( PartitionTuple([[3],[1],[2,2,1]]) )
False
sage: lam.dominates( PartitionTuple([[3],[2],[1,1,1]]))
True
sage.combinat.partition_tuple.PartitionTuples

Class of all partition tuples.

For more information about partition tuples, see PartitionTuple.

This is a factory class which returns the appropriate parent based on the values of level, size, and regular

INPUT:

  • level – the length of the tuple
  • size – the total number of cells
  • regular – the highest multiplicity an entry may have in a component plus \(1\)
sage.combinat.partition_tuple.PartitionTuples_all

Class of partition tuples of a arbitrary level and arbitrary sum.

sage.combinat.partition_tuple.PartitionTuples_level

Class of partition tuples of a fixed level, but summing to an arbitrary integer.

sage.combinat.partition_tuple.PartitionTuples_level_size

Class of partition tuples with a fixed level and a fixed size.

sage.combinat.partition_tuple.PartitionTuples_size

Class of partition tuples of a fixed size, but arbitrary level.

sage.combinat.partition_tuple.RegularPartitionTuples

Abstract base class for \(\ell\)-regular partition tuples.

sage.combinat.partition_tuple.RegularPartitionTuples_all

Class of \(\ell\)-regular partition tuples.

sage.combinat.partition_tuple.RegularPartitionTuples_level

Class of \(\ell\)-regular partition tuples with a fixed level.

sage.combinat.partition_tuple.RegularPartitionTuples_level_size

Class of \(\ell\)-regular partition tuples with a fixed level and a fixed size.

sage.combinat.partition_tuple.RegularPartitionTuples_size

Class of \(\ell\)-regular partition tuples with a fixed size.