Young Tableau: Introduction (Part I)

View literate file on Github

I have a book sitting on my shelf: Young Tableaux by William Fulton (ISBN 0 521 56724 6). I bought it after having the fantastic chance to see these beautiful and deep combinatorial structures in a couple of math courses. So, as I work through this book, I will be illustrating Young tableux and associated algorithms with Haskell. The great advantage of this subject is that we can explore it in pictures. I intend to do just this.

In this first post, let’s look at what a Young Tableux looks like. I will only list the essential definitions for the sake of brevity and to avoid replicating too much material from the book.

> {-# LANGUAGE NoMonomorphismRestriction #-}
> import Diagrams.Prelude
> import Diagrams.Backend.Cairo.CmdLine

A Young Diagram is a drawing of a partition \lambda = (\lambda_1, \dots, \lambda_k) such that each \lambda_i > \lambda_{i+1} where \lambda_i is represented as a row of boxes aligned to the left.

A single box can be rendered as

> box :: Diagram B R2
> box =  square 0.2 # fc white

and, we represent a set of rows of boxes as the following type along with a method to draw the Young diagram corresponding to a partition.

> type YoungDiagram a = [[a]]
> 
> youngDiagram :: [Int] -> YoungDiagram (Diagram B R2)
> youngDiagram = map (flip replicate box)
> 
> draw :: YoungDiagram (Diagram B R2) -> Diagram B R2
> draw = vcat . map hcat

Here is how the partition \lambda = (6,4,4,2) looks like as a Young diagram rendered as draw (youngDiagram [6,4,4,2])

Example of a young diagram

Example of a young diagram

Given a young diagram \mu contained in \lambda one can construct a skew diagram or skew shape, \lambda / \mu as the diagram obatained by removing a smaller Young diagram from the larger one.

> skew :: [Int] -> YoungDiagram (Diagram B R2)
> skew = map (flip replicate shadedCell)
> 
> shadedCell :: Diagram B R2
> shadedCell =  square 0.2 # fc green

The following is the skew shape for \lambda = (6,4,4,2) and \mu = (3,3,1) rendered as draw (skew [3,3,1]) <> draw (youngDiagram [6,4,4,2])

Example of a skew diagram

Example of a skew diagram

Finally, a young tableau is a filling of a young diagram that is

  1. weakly increasing across each row
  2. strictly increasing down each column
> numbering :: [[Int]] -> YoungDiagram (Diagram B R2)
> numbering = map (map (\x -> text (show x) # fontSizeN 0.1 # fc black))
> 
> zipDiagrams :: YoungDiagram (Diagram B R2) -> YoungDiagram (Diagram B R2)
>             -> YoungDiagram (Diagram B R2)
> zipDiagrams = zipWith (zipWith (<>))
> 
> youngTableau :: [Int] -> [Int] -> [[Int]] -> Diagram B R2
> youngTableau shape skewShape nums =
>     draw (skew skewShape)
>     <> draw (numbering nums `zipDiagrams` youngDiagram shape)

Here are two examples rendered by

    youngTableau [3,3,1] [] [[1,2,2],[2,3,3],[4]]
||| strutX 1
||| youngTableau [2,2,1] [1,1] [[2,2],[3],[3]]
Example of young and skew tableau

Example of young and skew tableau

Next time, I’ll work through the bumping and sliding algorithms and hopefully explore it with animation support in diagrams.

Advertisements
This entry was posted in Combinatorics, Haskell, Series and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s