1
$\begingroup$

Is there a name or characterization for the "partition" lattice of integer partitions of some n?

Young's Lattice depicts the integer partitions of numbers. Often Young diagrams are used in displaying the lattice as in this picture of Young's Lattice up to n=7. In this Hasse diagram an arrow mean adding 1 box in a connected position.

I'm not asking about this lattice's partial order, but about the partial order that can be imposed within each (equal rank) row of it.

For example, for $n=6$ the 11 row elements could be encoded as

6, 51, 42, 33, 411, 321, 222, 3111, 2211, 21111, 111111

These elements can be partially ordered. In the Hasse diagram of this order, an arrow means joining two partitions. Eg. since $1+1 = 2$ there is an arrow $411\to 42$. Likewise there is one $411\to 51$.

Here are diagrams I drew for partition lattices of integer partitions for 1 through 7 .

I'm guessing somebody has studied these lattices but I can't guess the right terminology to search for information or references or find that there is some other way of generating them.

These lattices come up in characterizing the monoid of endofunctions (a category) on an $n$ element set, $End(n)$. There is a map from each endofunction $f$ of $End(n)$ to the integer partition lattice $IP(n)$, $ip: End(n) \to IP(n)$. For function composition we have $ip(fg) = ip(gf)$ and $ip(fg) \ge ip(f)\vee ip(g)$.

(why are there no available tags for words I've bolded in this post?)

$\endgroup$
  • $\begingroup$ Minor point: you probably don't want to call these Hasse diagrams "partition lattices" since they're not lattices. For example, in the poset of partitions of 5, what is the least upper bound of {311, 221}? Perhaps you could call them "partition poset diagrams?" (not to mention, the name "partition lattices" is already taken) $\endgroup$ – William DeMeo Nov 24 '15 at 5:26
0
$\begingroup$

A starting point for a bibliographic search would be

Ziegler, Günter M. "On the poset of partitions of an integer." Journal of Combinatorial Theory, Series A 42.2 (1986): 215-222, doi:10.1016/0097-3165(86)90092-0

$\endgroup$
0
$\begingroup$

I am no mathematician, I apologize in advance. Solving a riddle, though, I came across a way to generate these partitions and induce an partial ordering on them. This is due to Knuth and others (see references in the first link below).

The keywords to look for would be "The Fenner-Loizou tree", "integer partitions tree" or "lexicographical ordering on integer partitions".

To recursively construct this, start with the partition "111...1", and at each step either add the 2 left-most 1's to form a "2", or add the rightmost non-1 with the 1 following it. If either of these operations are possible it creates a branch under the current node (in the tree), giving at most 2 branches per node.

Here's what I found:

http://www.luschny.de/math/seq/CountingWithPartitions.html

http://ac.els-cdn.com/S0021869303007877/1-s2.0-S0021869303007877-main.pdf?_tid=023bcc36-b3d3-11e6-b1ae-00000aacb35f&acdnat=1480163133_e8f521a129d615beeeb30e36c2e66e16

https://oeis.org/A228100

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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