Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Young's Lattice is the lattice of inclusions of Young tableaux, or integer partitions.

In R. Stanley's Enumerative Combinatorics Vol. 1, Proposition 1.4.4., there is a generalization of integer partitions where you limit the number of times each positive number may occur in the partition (and this limit may be zero).

Apparently, this gives a sublattice of Young's lattice -- where can I find a discussion of such sublattices in the literature? They may be discussed somewhere in Stanley's books but I can't seem to find them.

The particular case which i'm interested in is when only a given finite set of positive integers may occur, each of which at most a specified number of times. This produces a finite self-dual sublattice with many nice properties... do these lattices have a name?

For example, if 2 is allowed at most once and 1 is allowed at most twice, then we have the lattice

    (2,1,1)
       |  
     (2,1)  
    /     \
 (2)      (1,1)
    \     /
      (1)
       |
      ( )   

Another way of thinking of it would be as a lattice of subsequences of a finite sequence of weakly decreasing positive integers.

Update: such a lattice is a finite distributive lattice, so by the Birkhoff representation theorem, it is isomorphic to the lattice of lower sets of the poset of its join-irreducible elements. The posets in question are sub-posets of a certain infinite poset, but I am hoping for a description of this class of lattices which goes beyond simply identifying their Birkhoff representation.

share|improve this question
    
By "such sublattices" do you mean only the particular kind of sublattices of Young's lattice that Richard Stanley's book mentions? Or only the one you mention where you say "The particular case I'm interested in"? Or would you be interested in any other sorts? –  Michael Hardy Dec 4 '10 at 2:32
    
I'm happy to focus only on the lattice of subsequences of a finite sequence of weakly decreasing positive integers. –  Marco Gualtieri Dec 4 '10 at 2:41
    
Speaking in terms of Young diagrams, do such finite sublattices contain precisely the Young diagrams which are inside a given particular diagram? –  Leonid Petrov Dec 4 '10 at 21:17
    
@Lenoid: No, they are the diagrams which are inside the original, but you are only allowed deleting entire rows, not single blocks. –  Marco Gualtieri Dec 4 '10 at 21:27
add comment

1 Answer

up vote 2 down vote accepted

It appears these lattices can be described as a kind of twisted product of the simple lattice $[n]=\{0,1,2,\ldots, n-1\}$ with the usual order. To construct the lattice of subsequences of the sequence of weakly decreasing positive integers $(k_1,\ldots, k_N)$, let $m(k)$ be the multiplicity of the integer $k$ in the given sequence and form the product $$[d(1)]\times \cdots \times [d(N)],$$ equipped with the order $(a_1,\ldots, a_N)\leq (b_1,\ldots, b_N)$ iff $$a_N\leq b_N$$ $$a_N+a_{N-1}\leq b_N + b_{N-1}$$ $$\ldots$$ $$a_N+\cdots + a_1\leq b_N+\cdots + b_1.$$

For example, for the sequence $(3,2,1,1)$, we have $d(1)=2$ and $d(2)=d(3)=1$, so that the lattice is given by $[2]\times [1]\times [1]$, with the order given above.

This must be a standard construction in poset/lattice theory, please let me know if you've seen it somewhere.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.