Cat::CombinatorialModule – the category of combinatorial modules

Cat::CombinatorialModule represents the category of combinatorial modules.

→ Examples

Details:

Entries

"moduleGenerators"

This mandatory list contains the generators of the module.

"operators"

This mandatory entry implements the operators acting on the module.  In the simplest form, this entry can be a simple list of functions which each take an element of math to another element of math. In that case, the operators are indexed by math.  It is often natural to consider partial operators which are only defined on a subset of math. In that case, they may return the value FAIL.  For maximal flexibility, the operators can be specified by a single function math that returns an associative container math which models the set of all the images math by the operators math. The index set math may model any finite set, and need not be the same for all math. This effectively allows for modelling any directed graph; the nodes are the elements of the module, and the edges are labelled by the indices of operators. The indices are mainly used as labels in the graph drawing functionnalities. 

list – list of elements of the module

Returns the list of all the elements of the module. The default implementation is to use successive application of the operators over the module generators and their successors (depth first search, with usual math time complexity and math memory complexity).

listGraded – graded list of elements of the module

Returns all the elements of the module, as a table associating to each rank the elements of that rank.

dotClass – the graph of the module, in dot format

Returns the graph depicting the structure of the module, as a string in dot format.

dotClassGraded – the graded graph of the module, in dot format

Returns the graph depicting the structure of the module, as a string in dot format, with extra layout information so that nodes of same rank are drawn at the same level.

The Depth option can specify the number of rows one likes to drawn in the graded graph.

When a function is called with the Fibers option, the graph of the combinatorial class is splitted in classes, see the example 1 for details.

Example 1:

We define the combinatorial module permutohedron of order 3:

domain permutohedron4

    inherits Dom::BaseDomain;

    category Cat::CombinatorialModule,

             Cat::FacadeDomain(DOM_LIST);

 

    moduleGenerators:= [[1,2,3,4]];

 

    operators:= [x-> combinat::words::swapDecrease(x,1),

                 x-> combinat::words::swapDecrease(x,2),

                 x-> combinat::words::swapDecrease(x,3)];

 

end:

Note that operators could alternatively be defined as a single function x -> [combinat::words::swapDecrease(x,i) $i=1..3].

Now, we generate the list of all the elements:

permutohedron4::list();

math

This one is the graded list:

permutohedron4::listGraded();

math

This is the dot graded expression of the domain:

print(Unquoted, permutohedron4::dotClassGraded())

digraph  G {

node [shape=plaintext];

N_1 [label = " [1, 2, 3, 4] " ];

N_2 [label = " [2, 1, 3, 4] " ];

N_1 -> N_2 [color = "#000000", fontcolor = "#000000", label = " 1 " ];

N_3 [label = " [1, 3, 2, 4] " ];

N_1 -> N_3 [color = "#000000", fontcolor = "#000000", label = " 2 " ];

N_4 [label = " [1, 2, 4, 3] " ];

N_1 -> N_4 [color = "#000000", fontcolor = "#000000", label = " 3 " ];

{rank=same; N_2; N_3; N_4; }

N_5 [label = " [2, 3, 1, 4] " ];

N_2 -> N_5 [color = "#000000", fontcolor = "#000000", label = " 2 " ];

N_6 [label = " [2, 1, 4, 3] " ];

N_2 -> N_6 [color = "#000000", fontcolor = "#000000", label = " 3 " ];

N_7 [label = " [3, 1, 2, 4] " ];

N_3 -> N_7 [color = "#000000", fontcolor = "#000000", label = " 1 " ];

N_8 [label = " [1, 3, 4, 2] " ];

N_3 -> N_8 [color = "#000000", fontcolor = "#000000", label = " 3 " ];

N_4 -> N_6 [color = "#000000", fontcolor = "#000000", label = " 1 " ];

N_9 [label = " [1, 4, 2, 3] " ];

N_4 -> N_9 [color = "#000000", fontcolor = "#000000", label = " 2 " ];

{rank=same; N_5; N_6; N_7; N_8; N_9; }

N_10 [label = " [3, 2, 1, 4] " ];

N_5 -> N_10 [color = "#000000", fontcolor = "#000000", label = " 1 " ];

N_11 [label = " [2, 3, 4, 1] " ];

N_5 -> N_11 [color = "#000000", fontcolor = "#000000", label = " 3 " ];

N_12 [label = " [2, 4, 1, 3] " ];

N_6 -> N_12 [color = "#000000", fontcolor = "#000000", label = " 2 " ];

N_7 -> N_10 [color = "#000000", fontcolor = "#000000", label = " 2 " ];

N_13 [label = " [3, 1, 4, 2] " ];

N_7 -> N_13 [color = "#000000", fontcolor = "#000000", label = " 3 " ];

N_8 -> N_13 [color = "#000000", fontcolor = "#000000", label = " 1 " ];

N_14 [label = " [1, 4, 3, 2] " ];

N_8 -> N_14 [color = "#000000", fontcolor = "#000000", label = " 2 " ];

N_15 [label = " [4, 1, 2, 3] " ];

N_9 -> N_15 [color = "#000000", fontcolor = "#000000", label = " 1 " ];

N_9 -> N_14 [color = "#000000", fontcolor = "#000000", label = " 3 " ];

{rank=same; N_10; N_11; N_12; N_13; N_14; N_15; }

N_16 [label = " [3, 2, 4, 1] " ];

N_10 -> N_16 [color = "#000000", fontcolor = "#000000", label = " 3 " ];

N_11 -> N_16 [color = "#000000", fontcolor = "#000000", label = " 1 " ];

N_17 [label = " [2, 4, 3, 1] " ];

N_11 -> N_17 [color = "#000000", fontcolor = "#000000", label = " 2 " ];

N_18 [label = " [4, 2, 1, 3] " ];

N_12 -> N_18 [color = "#000000", fontcolor = "#000000", label = " 1 " ];

N_12 -> N_17 [color = "#000000", fontcolor = "#000000", label = " 3 " ];

N_19 [label = " [3, 4, 1, 2] " ];

N_13 -> N_19 [color = "#000000", fontcolor = "#000000", label = " 2 " ];

N_20 [label = " [4, 1, 3, 2] " ];

N_14 -> N_20 [color = "#000000", fontcolor = "#000000", label = " 1 " ];

N_15 -> N_18 [color = "#000000", fontcolor = "#000000", label = " 2 " ];

N_15 -> N_20 [color = "#000000", fontcolor = "#000000", label = " 3 " ];

{rank=same; N_16; N_17; N_18; N_19; N_20; }

N_21 [label = " [3, 4, 2, 1] " ];

N_16 -> N_21 [color = "#000000", fontcolor = "#000000", label = " 2 " ];

N_22 [label = " [4, 2, 3, 1] " ];

N_17 -> N_22 [color = "#000000", fontcolor = "#000000", label = " 1 " ];

N_18 -> N_22 [color = "#000000", fontcolor = "#000000", label = " 3 " ];

N_23 [label = " [4, 3, 1, 2] " ];

N_19 -> N_23 [color = "#000000", fontcolor = "#000000", label = " 1 " ];

N_19 -> N_21 [color = "#000000", fontcolor = "#000000", label = " 3 " ];

N_20 -> N_23 [color = "#000000", fontcolor = "#000000", label = " 2 " ];

{rank=same; N_21; N_22; N_23; }

N_24 [label = " [4, 3, 2, 1] " ];

N_21 -> N_24 [color = "#000000", fontcolor = "#000000", label = " 1 " ];

N_22 -> N_24 [color = "#000000", fontcolor = "#000000", label = " 2 " ];

N_23 -> N_24 [color = "#000000", fontcolor = "#000000", label = " 3 " ];

}

 

Which produces this dot picture: 1 

Graph of the permutohedron of size 4

 

The Fibers option of the dotClassGraded function provides a way to restrict the permuthohedron to classes. The next example pictures the plactic classes, that is, the permutations that give the same tableau by the Schensted insertion algorithm.

permutohedron4::dotClassGraded(Fibers= (z -> combinat::tableaux::schensted(z)[1]))

The output produces this dot picture: 1 

Plactic classes on the permutohedron of size 4

 

Example 2:

In this example, we implement an (admittedly trivial) combinatorial module whose elements are math with two (partial) operators math and math such that math and math. We want the names math and math to appear as labels on the edges of the module graph. To this end, we define operators as a single function which returns both images math and math, and use the gadget combinat::classes::valuesOfTable to label them with the names math and math of the operators:

domain sl4

    inherits Dom::BaseDomain;

    category Cat::CombinatorialModule, Cat::FacadeDomain(DOM_INT);

 

    moduleGenerators:= [1];

 

    operators :=

    proc(m: dom)

    begin

        combinat::classes::valuesOfTable(

    e = if m > 1 then m-1 else FAIL end_if,

            f = if m < 5 then m+1 else FAIL end_if

)

    end_proc;

end_domain:

    sl4::list()

math

Changes in MuPAD 4.0

New Function.