3. Fundamental Families of Posets
SUBSETS OF A SET
In the first example we generate the lattice of subsets of a 4-element set,
and several combinatorial invariants. Remember that Subsets[4] is the
built-in "definition" of the poset, and sub4 is a "tag name" (chosen by the
user) to reference all of the objects associated with this poset.
Build[Subsets[4],sub4]
Building poset sub4 ...
Done
Once a poset has been "built", its Hasse diagram may be displayed:
Diagram[sub4]
-Graphics-
The coefficents of the rank generating function indicate how many elements are
at each rank. For the subset lattice, these are just binomial coeffients.
RGF[sub4]
2 3 4
1 + 4 q + 6 q + 4 q + q
P[sub4] is one of the three fundamental objects produced by the Build
command. It contains the labels of all of the elements just generated.
P[sub4]
{{1, 2, 3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2},
{1, 3}, {2, 3}, {1, 4}, {2, 4}, {3, 4}, {1}, {2}, {3}, {4}, {}}
A second fundamental object is the Rank[sub4], which shows the rank of each
element.
Rank[sub4]
{0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4}
We can inquire whether this poset is a lattice. The answer is, of course,
"yes".
LatticeQ[sub4]
True
The "Zeta Polynomial" Z[n] of a poset P counts the number of multichains x1²x2
... ² xn-1 that can be formed from the elements of P.
ZetaPoly[sub4,n]
4
n
When P is an interval [a,b] this is the same as the number of multichains
a = x0 ² x1 ² x2 ² ... ² xn = b
betwen a and b. The command ZetaPoly[name,a,b,n] computes the Zeta
polynomial of the interval [a,b] in P.
Table[
ZetaPoly[sub4,1,b,n],
{b,1,Card[sub4]}]
2 2 2 2 2 2 3 3 3 3 4
{1, n, n, n, n, n , n , n , n , n , n , n , n , n , n , n }
PERMUTATIONS: WEAK ORDER
The weak order on permutations is defined by saying that w covers u if w can
be obtained from u by transposing a pair of adjacent increasing elements.
Build[WeakS[4],weaks4]
Building poset weaks4 ...
Done
P[weaks4]
{{1, 2, 3, 4}, {2, 1, 3, 4}, {1, 3, 2, 4}, {1, 2, 4, 3},
{2, 3, 1, 4}, {2, 1, 4, 3}, {3, 1, 2, 4}, {1, 3, 4, 2},
{1, 4, 2, 3}, {3, 2, 1, 4}, {2, 3, 4, 1}, {2, 4, 1, 3},
{3, 1, 4, 2}, {1, 4, 3, 2}, {4, 1, 2, 3}, {3, 2, 4, 1},
{2, 4, 3, 1}, {4, 2, 1, 3}, {3, 4, 1, 2}, {4, 1, 3, 2},
{3, 4, 2, 1}, {4, 2, 3, 1}, {4, 3, 1, 2}, {4, 3, 2, 1}}
The Hasse diagram for this poset may also be regarded as Cayley graph for the
symmetric group S4, with respect to the generators (1,2), (2,3), (3,4). For
general Sn the Hasse diagram is a regular graph of degree n-1.
Diagram[weaks4]
-Graphics-
The rank generating function for the weak order factors nicely:
RGF[weaks4]
Factor[RGF[weaks4]]
2 3 4 5 6
1 + 3 q + 5 q + 6 q + 5 q + 3 q + q
2 2 2
(1 + q) (1 + q ) (1 + q + q )
The elements at each rank are stored and displayed in the order generated by
the Build command. The poset can look quite different if another order is
used. For example, the next command puts each rank into lexicographic
order.
SortByRanks[weaks4]
When elements are represented by lists (as in this case), the labels are
sometimes hard to read. Compact command makes lists into strings, and Relabel
replaces each label in P[weaks4] by its "compact" equivalent. (Other
relabeling functions may also be defined and used.)
Relabel[weaks4,Compact]
Diagram[weaks4,ShowLabels->True]
-Graphics-
When the poset is large, it is sometimes convenient to display the Hasse
diagram with thinner dots and lines. This is done withe the Thinnness option,
as shown below. Note: a similar effect can be achieved using the "Make Lines
Thin" menu command. However in Mathematica version 2.2 (unlike earlier
versions), this changes the screen display but has no effect on the printout.
Thus, if printed copy is desired, the Thinnness option should be used.
Build[WeakS[5],weaks5]
SortByRanks[weaks5]
Diagram[weaks5]
Diagram[weaks5,Thinness->.6]
Building poset weaks5 ...
Done
-Graphics-
-Graphics-
PERMUTATIONS: STRONG ORDER
The strong order on permutations (also known as the Bruhat order) is defined
by saying that w is less than or equal to u if u can be obtained from w a
sequence of length-increasing transpositions (not necessarily adjacent).
Build[StrongS[3],strong3]
Building poset strong3 ...
Done
Relabel[strong3,Compact]
Diagram[strong3,ShowLabels->True]
-Graphics-
Build[StrongS[4],strongs4]
Diagram[strongs4]
Building poset strongs4 ...
Done
-Graphics-
The strong order on Sn is not a lattice:
LatticeQ[strong3]
Not a lattice: P[3] and P[2] have no LUB.
False
PARTITIONS OF A SET: REFINEMENT ORDER
In the refinement order on partitions of a set, partition A is less than or
equal to partition B if every block of A is contained in a block of B.
Build[SetP[5],setp5]
Building poset setp5 ...
Done
The total number of partitions of a set of n elements is the nth Bell Number,
usually denoted Bn.
Card[setp5]
52
The numbers of elements at each rank are given by Stirling numbers of the
second kind. These may also be produced by the built-in Mathematica function
StirlingS2.
RGF[setp5]
2 3 4
1 + 10 q + 25 q + 15 q + q
Table[StirlingS2[5,k],{k,5,1,-1}]
{1, 10, 25, 15, 1}
The characteristic polynomial of a poset with a 0 and 1 is a generalization of
the chromatic polynomial of a graph. It is given by the formula
CharPoly(q) = · µ(0,x) qr(1) -r(x)
where r denotes the rank function, µ denotes the Mobius function, and the sum
is over all elements x in the poset. For the lattice of partitions of
{1,...,n} the characteristic polynomial is the chromatic polynomial of Kn,
the complete graph on n vertices (apart from a factor of q). This polynomial
is of course just
q (q-1) (q-2) ... (q-n+1)
Hence its coefficients are Stirling numbers of the first kind. This may be
checked using the built-in function StirlingS1.
CharPoly[setp5,q]
Factor[%]
2 3 4
24 - 50 q + 35 q - 10 q + q
(-4 + q) (-3 + q) (-2 + q) (-1 + q)
Table[StirlingS1[5,k],{k,1,5}]
{24, -50, 35, -10, 1}
Diagram[setp5,Thinness->.5]
-Graphics-
Partitions are represented in P[setp5] using "pointer" notation, i.e. by a
list in which the kth entry is equal to the smallest integer in the block
containing k.
P[setp5]
{{1, 2, 3, 4, 5}, {1, 1, 3, 4, 5}, {1, 2, 1, 4, 5}, {1, 2, 3, 1, 5},
{1, 2, 3, 4, 1}, {1, 2, 2, 4, 5}, {1, 2, 3, 2, 5}, {1, 2, 3, 4, 2},
{1, 2, 3, 3, 5}, {1, 2, 3, 4, 3}, {1, 2, 3, 4, 4}, {1, 1, 1, 4, 5},
{1, 1, 3, 1, 5}, {1, 1, 3, 4, 1}, {1, 1, 3, 3, 5}, {1, 1, 3, 4, 3},
{1, 1, 3, 4, 4}, {1, 2, 1, 1, 5}, {1, 2, 1, 4, 1}, {1, 2, 1, 2, 5},
{1, 2, 1, 4, 2}, {1, 2, 1, 4, 4}, {1, 2, 3, 1, 1}, {1, 2, 2, 1, 5},
{1, 2, 3, 1, 2}, {1, 2, 3, 1, 3}, {1, 2, 2, 4, 1}, {1, 2, 3, 2, 1},
{1, 2, 3, 3, 1}, {1, 2, 2, 2, 5}, {1, 2, 2, 4, 2}, {1, 2, 2, 4, 4},
{1, 2, 3, 2, 2}, {1, 2, 3, 2, 3}, {1, 2, 3, 3, 2}, {1, 2, 3, 3, 3},
{1, 1, 1, 1, 5}, {1, 1, 1, 4, 1}, {1, 1, 1, 4, 4}, {1, 1, 3, 1, 1},
{1, 1, 3, 1, 3}, {1, 1, 3, 3, 1}, {1, 1, 3, 3, 3}, {1, 2, 1, 1, 1},
{1, 2, 1, 1, 2}, {1, 2, 1, 2, 1}, {1, 2, 1, 2, 2}, {1, 2, 2, 1, 1},
{1, 2, 2, 1, 2}, {1, 2, 2, 2, 1}, {1, 2, 2, 2, 2}, {1, 1, 1, 1, 1}}
NON-CROSSING PARTITIONS.
A partition is non-crossing if, when represented as above using pointer
notation, it has no subsequence
{...,x,...,y,...,x,...,y,...}
with x not equal to y. The non-crossing partitions form a very interesting
sub-poset of SetP[n].
Build[NonXP[5],nxp5]
Building poset nxp5 ...
Done
Diagram[nxp5]
-Graphics-
LatticeQ[nxp5]
True
RGF[nxp5]
2 3 4
1 + 10 q + 20 q + 10 q + q
So it is a lattice, and is also rank-symmetric. It is interesting to note that
both the cardinality and the Mobius function (from bottom to top) are Catalan
numbers:
Card[nxp5]
42
Mu[nxp5][[1]]
{1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 2, 2, 2, 1, 1, 1, 2, 2,
1, 2, 1, 1, 1, 1, 2, 2, 1, 2, 1, 2, -5, -5, -2, -5, -2, -2, -5, -2,
-2, -5, 14}
The number of maximal chains (from bottom to top) equals nn-2, which is also
the number of spanning trees in the complete graph on n vertices. (This
remarkable result, as well as others mentioned in this section, are due to G.
Kreweras, Discrete Math. 1 (1972), 333-350.)
MaximalChainsDown[nxp5]
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 2, 2, 2, 3, 3, 2, 3, 2, 2,
2, 2, 3, 3, 2, 3, 2, 3, 16, 16, 9, 16, 9, 9, 16, 9, 9, 16, 125}
The elements of P[nxp5] are just partitions, expressed in the usual way using
pointer notation:
P[nxp5]
{{1, 2, 3, 4, 5}, {1, 1, 3, 4, 5}, {1, 2, 1, 4, 5}, {1, 2, 3, 1, 5},
{1, 2, 3, 4, 1}, {1, 2, 2, 4, 5}, {1, 2, 3, 2, 5}, {1, 2, 3, 4, 2},
{1, 2, 3, 3, 5}, {1, 2, 3, 4, 3}, {1, 2, 3, 4, 4}, {1, 1, 1, 4, 5},
{1, 1, 3, 1, 5}, {1, 1, 3, 4, 1}, {1, 1, 3, 3, 5}, {1, 1, 3, 4, 3},
{1, 1, 3, 4, 4}, {1, 2, 1, 1, 5}, {1, 2, 1, 4, 1}, {1, 2, 1, 4, 4},
{1, 2, 3, 1, 1}, {1, 2, 2, 1, 5}, {1, 2, 2, 4, 1}, {1, 2, 3, 2, 1},
{1, 2, 3, 3, 1}, {1, 2, 2, 2, 5}, {1, 2, 2, 4, 2}, {1, 2, 2, 4, 4},
{1, 2, 3, 2, 2}, {1, 2, 3, 3, 2}, {1, 2, 3, 3, 3}, {1, 1, 1, 1, 5},
{1, 1, 1, 4, 1}, {1, 1, 1, 4, 4}, {1, 1, 3, 1, 1}, {1, 1, 3, 3, 1},
{1, 1, 3, 3, 3}, {1, 2, 1, 1, 1}, {1, 2, 2, 1, 1}, {1, 2, 2, 2, 1},
{1, 2, 2, 2, 2}, {1, 1, 1, 1, 1}}
Next we investigate how NonXP[n] "sits" inside SetP[n]. The first step is use
LocateSet to determine which elements of P[setp5] correspond to elements of
P[nxp5]. (Be sure to Build P[setp5] before executing the next commands.)
nxpindices = LocateSet[setp5,P[nxp5]]
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
22, 23, 24, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 38, 39, 40, 42,
43, 44, 48, 50, 51, 52}
Now we can check some other things:
SubLatticeQ[setp5,nxpindices]
JoinSubLatticeQ[setp5,nxpindices]
MeetSubLatticeQ[setp5,nxpindices]
False
False
True
So the non-crossing partitions are closed under forming meets but not joins.
For example:
Vee[nxp5,{1,2,3,3,2},{1,2,1,4,5}]
{1, 1, 1, 1, 1}
Vee[setp5,{1,2,3,3,2},{1,2,1,4,5}]
{1, 2, 1, 1, 2}
Wedge[nxp5,{1,2,3,3,2},{1,2,1,4,5}]
{1, 2, 3, 4, 5}
Wedge[setp5,{1,2,3,3,2},{1,2,1,4,5}]
{1, 2, 3, 4, 5}
Here is a diagram of SetP[5], highlighting the elements of NonXP[5]:
Diagram[setp5,nxpindices,Thinness->.6]
-Graphics-
LATTICE OF CONTRACTIONS OF A GRAPH.
If G is a graph with vertex set V, the set of partitions of V whose blocks are
G-connected forms a join-sublattice of the full partition lattice on V, called
the lattice of contractions of G. We illustrate by constructing this lattice
when G is a 5-cycle.
edgeset = {{1,2},{2,3},{3,4},{4,5},{5,1}};
Build[ContractionLattice[edgeset,5],cycle5]
Diagram[cycle5]
Building poset cycle5 ...
Done
-Graphics-
The elements of P[cycle5] are partitions of {1,2,3,4,5}, represented (as
before) using pointer notation.
P[cycle5]
{{1, 2, 3, 4, 5}, {1, 1, 3, 4, 5}, {1, 2, 2, 4, 5}, {1, 2, 3, 3, 5},
{1, 2, 3, 4, 4}, {1, 2, 3, 4, 1}, {1, 1, 1, 4, 5}, {1, 1, 3, 3, 5},
{1, 1, 3, 4, 4}, {1, 1, 3, 4, 1}, {1, 2, 2, 2, 5}, {1, 2, 2, 4, 4},
{1, 2, 2, 4, 1}, {1, 2, 3, 3, 3}, {1, 2, 3, 3, 1}, {1, 2, 3, 1, 1},
{1, 1, 1, 1, 5}, {1, 1, 1, 4, 4}, {1, 1, 1, 4, 1}, {1, 1, 3, 3, 3},
{1, 1, 3, 3, 1}, {1, 1, 3, 1, 1}, {1, 2, 2, 2, 2}, {1, 2, 2, 2, 1},
{1, 2, 2, 1, 1}, {1, 2, 1, 1, 1}, {1, 1, 1, 1, 1}}
Let's see what this set looks like, as a subset of P[set5].
c5indices = LocateSet[setp5,P[cycle5]]
{1, 2, 5, 6, 9, 11, 12, 14, 15, 17, 23, 27, 29, 30, 32, 36, 37, 38,
39, 40, 42, 43, 44, 48, 50, 51, 52}
SubLatticeQ[setp5,c5indices]
JoinSubLatticeQ[setp5,c5indices]
MeetSubLatticeQ[setp5,c5indices]
False
True
False
So, as remarked earlier, it is a join-sublattice of P[set5], but is not closed
under meets.
Diagram[setp5,c5indices,Thinness->.6]
-Graphics-
The characteristic polynomial of the lattice of contractions of a graph G is
equal to the chromatic polynomial of G (apart from a factor of q) .
CharPoly[cycle5,q]
2 3 4
4 - 10 q + 10 q - 5 q + q
It is well-known that the chromatic polynomial of an n-cycle can be expressed
by the formula
(q - 1)n + (-1)n (q - 1)
We can check the above result by computing, for n=5,
( (q-1)^n + (-1)^n (q-1) /. n->5 ) // Expand
2 3 4 5
4 q - 10 q + 10 q - 5 q + q
The coefficients of the characteristic polynomial (and in this case the
chromatic polynomial) are obtained by summing the Mobius function µ(0,x) over
each rank. This can be illustrated and checked by labelling each element by
its Mobius function value, as follows:
P[cycle5] = Mu[cycle5][[1]]
{1, -1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, 4}
Diagram[cycle5,ShowLabels->True]
-Graphics-
Observe that the sums of the labels across each row give the coefficients of
the chararacteristic polynomial.
YOUNGS LATTICE
Let L be a partition. Then YoungsLattice[L] is the poset consisting of
partitions whose Ferrers diagram fits inside the Ferrers diagram of L. The
partial ordering is by containment of diagrams. This turns out to be a
distributive lattice, and from its poset of join-irreducibles one recovers the
original Ferrers diagram of L. Maximal chains in YoungsLattice[L] are in
one-to-one correspondence with standard Young tableaux of shape L.
Build[YoungsLattice[{5,2,2,1,1}],y52211]
Building poset y52211 ...
Done
The list P[y52211] contains all partitions whose Ferrers diagram fits inside
the Ferrers diagram of L = {5,2,2,1,1}.
P[y52211]
{{5, 2, 2, 1, 1}, {4, 2, 2, 1, 1}, {5, 2, 1, 1, 1}, {5, 2, 2, 1, 0},
{3, 2, 2, 1, 1}, {4, 2, 1, 1, 1}, {4, 2, 2, 1, 0}, {5, 1, 1, 1, 1},
{5, 2, 1, 1, 0}, {5, 2, 2, 0, 0}, {2, 2, 2, 1, 1}, {3, 2, 1, 1, 1},
{3, 2, 2, 1, 0}, {4, 1, 1, 1, 1}, {4, 2, 1, 1, 0}, {4, 2, 2, 0, 0},
{5, 1, 1, 1, 0}, {5, 2, 1, 0, 0}, {2, 2, 1, 1, 1}, {2, 2, 2, 1, 0},
{3, 1, 1, 1, 1}, {3, 2, 1, 1, 0}, {3, 2, 2, 0, 0}, {4, 1, 1, 1, 0},
{4, 2, 1, 0, 0}, {5, 1, 1, 0, 0}, {5, 2, 0, 0, 0}, {2, 1, 1, 1, 1},
{2, 2, 1, 1, 0}, {2, 2, 2, 0, 0}, {3, 1, 1, 1, 0}, {3, 2, 1, 0, 0},
{4, 1, 1, 0, 0}, {4, 2, 0, 0, 0}, {5, 1, 0, 0, 0}, {1, 1, 1, 1, 1},
{2, 1, 1, 1, 0}, {2, 2, 1, 0, 0}, {3, 1, 1, 0, 0}, {3, 2, 0, 0, 0},
{4, 1, 0, 0, 0}, {5, 0, 0, 0, 0}, {1, 1, 1, 1, 0}, {2, 1, 1, 0, 0},
{2, 2, 0, 0, 0}, {3, 1, 0, 0, 0}, {4, 0, 0, 0, 0}, {1, 1, 1, 0, 0},
{2, 1, 0, 0, 0}, {3, 0, 0, 0, 0}, {1, 1, 0, 0, 0}, {2, 0, 0, 0, 0},
{1, 0, 0, 0, 0}, {0, 0, 0, 0, 0}}
Relabel[y52211,Compact] ;
Diagram[y52211, ShowLabels->True,Thinness->.8]
-Graphics-
For technical reasons this poset has been generated "upside down". We could
turn it right side up using the Build[Dual[...],...] command, but this will
not be illustrated here.
We get the number of standard Young tableaux associated with each element of
P[y52211] by computing maximal chains, as follows:
MaximalChainsUp[y52211]
{1540, 567, 448, 525, 162, 189, 216, 70, 189, 120, 28, 64, 70, 35,
90, 56, 35, 64, 14, 14, 15, 35, 21, 20, 35, 15, 14, 5, 9, 5, 10,
16, 10, 9, 5, 1, 4, 5, 6, 5, 4, 1, 1, 3, 2, 3, 1, 1, 2, 1, 1, 1, 1,
1}
P[y52211] is a distributive lattice, and thus its join- and meet-irreducibles
are of particular interest. In fact we would like to identify the entire
"poset of join-irreducibles", for separate study. The following command
locates the indices of the join-irreducibles.
JI[y52211]
{2, 3, 4, 5, 8, 10, 11, 27, 36, 42, 54}
Next we produce another diagram of P[y52211], with the join-irreducibles
highlighted. Since it is usually difficult (in large cases) to verify the
order relation visually, we can also highlight
cover relations in the poset of join-irreducibles. (Any subposet or
collection of links may be displayed this way).
Diagram[y52211,JI[y52211],JICoverRelations[y52211]]
-Graphics-
In the shaded segments of the subposet one can see the Ferrers diagram for
{5,2,2,1,1}. The poset itself can be extracted using the SubPoset command. To
use this command, one needs the name of the original poset, as well as a set
of indices to pick out. (The indices may be generated in other ways; see
Section 4 for more examples and further discussion of the SubPoset command.)
indices = JI[y52211];
Build[SubPoset[y52211,indices],jisub]
Diagram[jisub]
Building poset jisub ...
Done
-Graphics-
Unfortunately the package is not able to make it "look" any more like a
Ferrers diagram than this!
DIVISORS OF AN INTEGER
The divisors of N form a poset (actually a distributive lattice) under the
divisibility relation. Each element (an integer) may be identified with the
multiset of primes occurring in its prime factorization. Hence this lattice
may also be viewed as the lattice of multisubsets of a multiset. When N is
squarefree, it is just a subset lattice.
Build[Div[210],d210]
Diagram[d210,ShowLabels->True]
Building poset d210 ...
Done
-Graphics-
FactorInteger[210]
{{2, 1}, {3, 1}, {5, 1}, {7, 1}}
Build[Div[288],d288]
Diagram[d288,ShowLabels->True]
Building poset d288 ...
Done
-Graphics-
FactorInteger[288]
{{2, 5}, {3, 2}}
It is well-known that this poset is a distributive lattice. In general, the
command DistributiveLatticeQ can be used to test this property.
DistributiveLatticeQ[d288]
The poset is strongly ranked.
True
The Mobius function of this poset is the "classical" number-theoretic Mobius
function. In this context, its values may defined as the entries of the
inverse of the Zeta-matrix of P. We illustrate by showing the first row of
both the Zeta-matrix and the Mu-matrix.
ZetaP[d288][[1]]
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Mu[d288][[1]]
{1, -1, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Exercise for the reader: what formula generates the numbers illustrated by the
next command?
MaximalChainsDown[d288]
{1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 4, 6, 1, 5, 10, 6, 15, 21}
PARTITIONS OF AN INTEGER N : REFINEMENT ORDER
Partitions of fixed integer N form a poset under the "refinement" ordering
(the definition should be clear). It is a curious poset, because most of the
known results concerning it are negative. For example, it is not a lattice,
it's Mobius function does not alternate in sign, etc. Is there anything nice
to say about this poset?
Build[NumP[8],nump8]
Building poset nump8 ...
Done
P[nump8]
{{8}, {1, 7}, {2, 6}, {3, 5}, {4, 4}, {1, 1, 6}, {1, 2, 5},
{1, 3, 4}, {2, 2, 4}, {2, 3, 3}, {1, 1, 1, 5}, {1, 1, 2, 4},
{1, 1, 3, 3}, {1, 2, 2, 3}, {2, 2, 2, 2}, {1, 1, 1, 1, 4},
{1, 1, 1, 2, 3}, {1, 1, 2, 2, 2}, {1, 1, 1, 1, 1, 3},
{1, 1, 1, 1, 2, 2}, {1, 1, 1, 1, 1, 1, 2}, {1, 1, 1, 1, 1, 1, 1, 1}}
Relabel[nump8,Compact]
Diagram[nump8,ShowLabels->True]
-Graphics-
This poset is definitely not a lattice, as the following shows:
LatticeQ[nump8]
Not a lattice: P[3] and P[2] have no LUB.
False
Question: does anybody know a formula for these numbers?
MaximalChainsDown[nump8]
{1, 1, 1, 1, 1, 2, 3, 3, 2, 2, 5, 10, 7, 10, 2, 15, 32, 22, 47, 69,
116, 116}
MaximalChainsUp[nump8]
{116, 33, 37, 27, 19, 11, 12, 10, 9, 5, 4, 5, 2, 3, 1, 2, 2, 1, 1, 1,
1, 1}
PARTITIONS OF AN INTEGER N: DOMINANCE ORDER
The partitions of a fixed integer N have another natural ordering, defined as
follows. We say that A is less than or equal to B if, for all k, the sum of
the k largest parts of A is less than or equal to the sum of the k largest
parts of B. This is known as the dominance, or majorization order, and gives a
poset with extremely interesting properties. For example, it is always a
lattice, and is always self-dual. But is is not ranked! The dominance order
appears naturally in problems related to symmetric functions, characters of
Sn, zero-one matrices, and many other subjects. For an extensive survey, see
the book by A. W. Marshall and I. Olkin, "Inequalities: Theory of Majorization
and its Applications", Academic Press (1979).
Build[MajP[9],majp9]
Building poset majp9 ...
Done
P[majp9]
{{9}, {8, 1}, {7, 2}, {6, 3}, {7, 1, 1}, {5, 4}, {6, 2, 1},
{5, 3, 1}, {6, 1, 1, 1}, {4, 4, 1}, {5, 2, 2}, {5, 2, 1, 1},
{4, 3, 2}, {4, 3, 1, 1}, {5, 1, 1, 1, 1}, {3, 3, 3}, {4, 2, 2, 1},
{4, 2, 1, 1, 1}, {3, 3, 2, 1}, {3, 3, 1, 1, 1}, {4, 1, 1, 1, 1, 1},
{3, 2, 2, 2}, {3, 2, 2, 1, 1}, {3, 2, 1, 1, 1, 1}, {2, 2, 2, 2, 1},
{2, 2, 2, 1, 1, 1}, {3, 1, 1, 1, 1, 1, 1}, {2, 2, 1, 1, 1, 1, 1},
{2, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1}}
The command RankedQ tests whether a poset is ranked. If it is not ranked, the
data contaned in Rank[name] is automatically redefined so that the rank of an
element x equals the length of the longest chain descending from x. (This is
also sometimes called the height of x.) It is important to apply this
operation to posets that aren't ranked, since the package can produce strange
results (even errors) otherwise.
RankedQ[majp9]
The poset is not ranked.
False
The package also identifies the intermediate property of being "weakly"
ranked, as opposed to being "strongly" ranked. In the former case, there
exists a rank function that respects coverings. In the latter, the minimal
elements must all have rank zero. The poset P[majp9] is neither strongly nor
weakly ranked.
Relabel[majp9,Compact]
Diagram[majp9,ShowLabels->True]
-Graphics-
We can check the new data in Rank[majp9] by using it to "relabel" P[majp9],and
then displaying the result. This is often a good way to represent poset data
graphically.
P[majp9] = Rank[majp9];
Diagram[majp9,ShowLabels->True]
-Graphics-
P[majp9] has a peculiar structure, but it does turn out to be a lattice.
LatticeQ[majp9]
True
And it is also self-dual.
Build[Dual[majp9],dualp9]
Building poset dualp9 ...
Done
Diagram[dualp9]
-Graphics-
The package contains a "tentative" isomorphism test. If P fails certain tests,
it returns False. Otherwise, if it passes them all, the result is Probably.
IsomorphicQ[majp9,dualp9]
Probably
RANDOM POSETS
Random posets may be produced with the command Build[Random[N,p]], which
generates ordered pairs{a,b} satisfying a<b, each with probability p, and
then forms the transitive closure.
Build[RandomP[21,.5],ran21]
Building poset ran21 ...
Done
Since these random posets are rarely ranked, the Hasse diagram often looks
"wrong" unless the standard uniform alignment of vertices is perturbed
slightly. This is done with the Jiggled option, whose integer values control
the amount of perturbation.
RankedQ[ran21]
The poset is not ranked.
False
Diagram[ran21,Jiggled->3,ShowLabels->True]
As noted before, when a poset is not ranked and RankedQ is called, the Rank
object is redefined so that the rank of an element equals its "height", i.e.,
length of the longest chain descending from it, minus one. Exercise: verify
this for the above poset. Second exercise: re-display the poset with labels
showing the height of each element.
Rank[ran21]
{0, 0, 0, 1, 1, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8, 9, 10,
11, 11, 11}
P[ran21]
{1, 2, 5, 3, 8, 4, 6, 7, 9, 10, 11, 13, 12, 14, 15, 16,
17, 18, 19, 20, 21}