vendredi 15 mars 2013

Promotion and growth diagrams

Here is the picture associated with dual evacuation (with an svg version):

This time the skew tableau t is depicted by the top row, and next rows, downward, result from successive dual evacuations of elements of t, selected in decreasing order.

The local commutativity rules enable us to build the whole family of diagrams, from the top row and from the diagonal, where all partitions are equal to the outer shape of t. The first column depicts the tableau ε*(t), and symmetry between rows and columns yields a 2d-proof that dual evacuation ε* is an involution.

This dual version of the preceding post would be of little interest, if it was not a preamble to a much nicer formula involving promotion. This operator ∂ is defined like evacuation of the minimal element, except that we put in the cell freed by this evacuation, a new entry larger than any other. The following picture shows p successive applications of ∂ to a tableau t (bottom row), where p is the size of t, i.e., the number of entries:

(here is an svg version).

Because the local rules that allow us to build the picture from the bottom row and from one of the diagonals are always the same, we discover that the left half of the picture, bordered by the central column, is exactly the same as the picture associated to evacuation, published in the preceding post; and on the right half of the picture we recognize a dual evacuation, applied to the central column (beware that diagrams in this part of the picture are different from those located at the start of this post, because top row is different). Hence we get a very nice 2d-proof of the following formula, again due to Schützenberger:

p = ε ε*

where the operators are composed in the "right" order, i.e. first ε then ε*. The tableau ε(t) appears as the central column on this picture.

jeudi 14 mars 2013

"Jeu de taquin" and growth diagrams

Growth diagrams yield a 2d-view of transformations involved in "jeu de taquin", a creation of Marcel-Paul Schützenberger, see Promotion and Evacuation by Richard P. Stanley, 2009. Here is a 2d-proof that evacuation (as defined by Schützenberger) is an involution:

This picture is constructed using a personal little Sage module, about skew tableaux. The standard module sage.combinat.skew_tableau is, as usual for enumerative combinatorics, useless. Here is an svg version of the picture.

Each row depicts a skew tableau as a sequence of growing diagrams: each diagram depicts a partition, and differs from the preceeding (in the same row) by adding a single cell, depicted by a blue square. Likewise each column is made (downward) by increasing diagrams, where the red square denotes the added cell. Green squares denote cells which are "simultaneously blue and red" (I know, this way of mixing colors is definitely wrong).

Here the bottom row is a given skew tableau t, and successive rows, bottom-up, result from successive evacuations of elements of t, as defined by Schützenberger.

The key observation is the local commutativity rule, which is equivalent to the definition of a taquin slide: starting from a diagram A, we may go right, where is the diagram B, then go down, where is D; or we may first go down, where is C, and then right, where is D. If blue and red squares involved are independent (i.e. they don't form a domino), these "two steps" walks differ by the order in which cells are added. Otherwise these walks are identical, D has an unique green square, that is a "free cell" during a "jeu de taquin" slide.

These rules allow to reconstruct the whole family of diagrams, from the initial tableau t, depicted by the bottom row, and from the diagonal, where all partitions are equal to the inner shape of t. The last column depicts the tableau ε(t) where ε denotes the evacuation operator, and because local commutativity rules are invariant by exchanging rows and columns, the bottom row depicts as well the tableau that results of applying ε to the last column. This is the expected 2d-proof that ε is an involution.

For the record let's look at the two bottom rows of the picture, to analyze their relationship with "jeu de taquin" sliding. The skew tableau t (bottom row) is the following left one, and the evacuation of entry 1 yield the next four tableaux, where a question mark ? denotes the "free cell" during sliding of the entries 1, 2, 5, 9. The last of these tableaux, on the right, results from this sliding:

* * 1 3 10    * * ? 3 10    * * 2 3 10    * * 2 3 10    * * 2 3 10
* * 2 5 11    * * 2 5 11    * * ? 5 11    * * 5 ? 11    * * 5 9 11
* 4 7 9       * 4 7 9       * 4 7 9       * 4 7 9       * 4 7 ?
6 8 12        6 8 12        6 8 12        6 8 12        6 8 12

Compare with the two bottom rows of the main picture, reproduced here for convenience:

In the bottom row, diagrams 1, 2, 5, 9 (with numbering starting at 0) have a green cell, in the same position as the question mark identifying free cell in "jeu de taquin"; other diagrams have a red cell, in the same position as the preceeding green one. It should be clear that on the other hand, this description of green and red cells results precisely from the local commutativity rules, and yields the top row among these two.

Note: jeu de taquin, promotion, evacuation and growth diagrams make sense for any finite poset, see Schützenberger and the cited article by Richard Stanley. This post is about the seminal case, where the underlying poset is N x N, and finite ideals are partitions, which form the Young lattice.

jeudi 16 février 2012

Dessiner un tas de sable (plot)

Pour afficher un tas de sable avec Sage il faut définir une méthode plot(), comme dans le module standard de David Perkinson. Ici je ne m'intéresse qu'aux tas de sable sur une grille rectangulaire, et je vais donc écrire une méthode pour la classe ConfigGrid :

from sage.plot.colors import Color
from sage.plot.plot import Graphics
from sage.plot.line import line
from sage.plot.text import text
from sage.plot.scatter_plot import scatter_plot
[...]
class ConfigGrid (Configuration):
    def __init__ (self, m, n, sable = 0):
        g = SandpileGrid (m, n)
        Configuration.__init__ (self, g, sable)
        
    def stabilize(self):
        [...]

    def plot (self, palette=0, cell=None, composition='', **kwds):

Le premier argument, palette, est probablement inattendu, mais j'aime bien pouvoir varier les palettes de couleurs, j'en reparlerai. Je souhaite afficher une configuration comme un ensemble de cellules, rondes a priori, avec pour chacune le nombre de grains de sable, indiqué à la fois par une couleur et par un chiffre (ou plusieurs). Le second argument, cell, désigne la taille de chaque cellule, et le troisième, composition, sert à spécifier des options, j'en reparlerai. Enfin la méthode admet des arguments complémentaires en nombre indéfini, passés sous la forme keyword=value, selon un protocole Python simple, agréable, et classique.

La méthode plot() retourne un objet graphique, appelé traditionnellement G, et constitué de primitives graphiques, qu'on ajoute une à une à G. Ici la primitive essentielle est fournie par la fonction scatter_plot() :

    def plot (self, palette=0, cell=None, composition='', **kwds):
        m = self.sandpile.nbrows
        n = self.sandpile.nbcols
        
        # ms = marker size
        dmax = max (m, n)
        if dmax < 10: ms = 500
        else:  ms = 4000 // dmax
        # l'argument l'emporte, s'il est fourni
        if cell != None: ms = cell
            
        G = Graphics()
        p = [[x, m-y-1] for y in range(m) for x in range(n)]
        c = [couleur(self[i+1, j+1]) for i in range(m) for j in range(n)]
        ec = 'black'    # edgecolor
        # scatter_plot : zorder = 5 par défaut
        # on peut modifier les options 'marker' et 'alpha'
        # exemple: plot (palette=3, marker='s')
        s = scatter_plot (p, markersize = ms,
            facecolor = c, edgecolor = ec, **kwds)
        G += s

La fonction scatter_plot() prend en argument une liste de points, qui seront représentés par des marques (disque, carré, croix, etc); il faut prendre garde au piège habituel : la ligne i correspond à l'ordonnée y renversée (la ligne 1 est en haut, etc), tandis que la colonne j correspond à l'abscisse x. La fonction admet ensuite des arguments optionnels : taille des marques, couleur, et couleur de leur bord. La spécification des couleurs est très souple, et peut être une liste : ici chaque couleur dépend du nombre de grains de sable et de la palette, je ne donnerai pas le code de la fonction couleur (il est très simple, il faut juste faire attention à utiliser les palettes de manière circulaire).

La fonction scatter_plot() admet deux autres arguments optionnels, indiqués dans le code ci-dessus, et récupérés automatiquement s'ils sont fournis lors de l'appel à la méthode plot(), grâce à **kwds. De son côté elle transmet d'éventuels arguments inconnus d'elle à la méthode show(), qui affiche un objet graphique.

Tracer les lignes de la grille est très simple, on utilise la primitive graphique line() :

        for i in range (m):
            G += line ([(-0.5, i),(n-0.5, i)])
        for j in range (n):
            G += line ([(j, -0.5),(j, m-0.5)])

Ces lignes passent sous les cellules dessinées par scatter_plot(), comme par magie : en fait l'ordre de superposition des composantes d'un objet graphique est déterminé par le paramètre zorder, qui vaut 0 par défaut pour line(), et 5 pour scatter_plot().

Il ne reste plus qu'à ajouter la représentation décimale de chaque altitude, si on le souhaite, en utilisant la primitive graphique text() :

        fs = 8 + ms // 50
        G += sum (text (str(self[i+1, j+1]), (j, m-i-1),
                        fontsize = fs, zorder = 10)
                  for i in range (m) for j in range (n))

Comme d'habitude il faut écrire soigneusement la correspondance entre le couple (ligne, colonne) de la configuration, et le couple (x, y) sur le dessin. Le paramètre zorder spécifie que le texte est visible, car placé au-dessus des marques dessinées par scatter_plot().

La fin du code de plot() se comprend d'elle-même :

        G.xmin(-1)
        G.xmax(n)
        G.ymin(-1)
        G.ymax(m)
        G.axes(False)
        G.set_aspect_ratio(1)
        return G

Le code de la méthode ConfigGrid.plot() est maintenant presque complet. Je ne donne pas les palettes, ce sont de simples listes de couleurs, que je suis allé chercher sur le site Color Brewer — le graphisme est un métier.

Quand on utilise cette méthode, on souhaite rapidement disposer de pas mal d'options : afficher ou non les lignes, les chiffres, etc. Le premier réflexe est d'ajouter des paramètres un à un, mais on est rapidement débordé. J'ai choisi d'ajouter un seul paramètre composition, qui est une chaîne de caractères, chaque option étant repérée par une lettre, d'où par exemple le fragment de code suivant :

        digits = dmax < 80
        if 'd' in composition:
            digits = not digits

et le code donné un peu plus haut pour afficher les altitudes avec la primitive text() est gardé par :

        if digits:

Je peux ainsi basculer le choix par défaut (chiffres affichés pour les grilles de côtés inférieurs à 80). Voici quelques exemples de ce que je peux obtenir :

c=ConfigGrid (6, 8, 4); c.stabilize(); c.plot()
c=ConfigGrid (100, 100, 12)
c.stabilize()
c.plot(palette=2, figsize=12)

L'option 'q' permet d'afficher seulement le quart nord-ouest de la grille :

c.plot(palette=2, composition='q', figsize=12)

L'option 'b' supprime le bord de chaque cellule, l'option 'd' supprime l'affichage des chiffres, l'option 'l' supprime l'affichage des lignes de la grille, et 's' désigne une marque carrée (square) :

c.plot(palette=4, cell=20, composition='bdlq', marker='s')