4. Operations on Posets
ELEMENTARY CONSTRUCTIONS
In this section we illustrate some simple commands for building new posets
from old ones: DisjointSum, OrdinalSum, and CartesianProduct. (The commands
SubPoset and Dual have already been illustrated in previous sections.) The
commands in this section have both long and short forms, e.g., DisjointSum
may also be abbreviated DS. The commands DS, OS, and CP may take as argument
any poset definition (e.g. Chain[n]), or the "name" of another poset that has
been constructed. As a result, they can be composed to form very complicated
sequences of operations.
The examples also illustrate that if a "name" is not provided to Build, it
constructs one automatically, i.e. Poset1, Poset2, etc.
First, the disjoint sum of a 3-element chain and a 4-element chain.
Build[DS[Chain[3],Chain[4]]]
Building poset Poset1 ...
Done
Diagram[Poset1]
-Graphics-
Next we take the cartesian product of the last poset (named Poset1) with a
3-element chain.
Build[CP[Poset1,Chain[3]]]
Diagram[Poset2]
Building poset Poset2 ...
Done
-Graphics-
Next we construct something much more complicated. Here OS means "ordinal
sum", the operation of placing one poset above another.
strange = CP[OS[Chain[3],DS[Chain[2],Chain[4]]],Chain[3]];
Build[strange]
Building poset Poset3 ...
Done
Notice that strange is not the "name" of the poset, but its "definition". The
tag name in this case is Poset3.
Diagram[Poset3]
-Graphics-
SELECTING A SUB-POSET
It is often convenient to define posets as subposets of another poset, with
the induced partial order. The SubPoset command takes as input either by a
list of positions, or as a Boolean function which picks out positions in
P[name] automatically. We illustrate both methods by constructing the poset of
subsets of 1...N whose sum is even, for N=5 and N=7.
Build[Subsets[5],sub5]
Building poset sub5 ...
Done
Here is a Boolean function that returns True if the sum is even.
evensumQ[s_] := EvenQ[Apply[Plus,s]]
Using it, we produce the indices of the desired subposet.
evensets = Position[Map[evensumQ,P[sub5]],True] // Flatten
{2, 4, 6, 7, 9, 11, 13, 14, 16, 18, 21, 23, 25, 28, 30, 32}
Build[SubPoset[sub5,evensets],even5]
Building poset even5 ...
Done
By default, the SubPoset command returns a poset with "generic" labels, i.e.
the integers 1...Card[P]. A special command recovers the correct labels from
the original poset, and relabels the subposet.
RestoreSubPosetLabels[sub5,evensets,even5]
P[even5]
{{1, 2, 3, 4}, {1, 2, 4, 5}, {2, 3, 4, 5}, {1, 2, 3}, {1, 3, 4},
{1, 2, 5}, {2, 3, 5}, {1, 4, 5}, {3, 4, 5}, {2, 4}, {1, 3}, {1, 5},
{3, 5}, {2}, {4}, {}}
Relabel[even5,Compact]
Diagram[even5,ShowLabels->True]
-Graphics-
The second method is to supply evensumQ as an argument to Subposet.
Build[Subsets[6],sub6]
Build[SubPoset[sub6,evensumQ],even6]
Building poset sub6 ...
Done
Building poset even6 ...
Done
RestoreSubPosetLabels[sub6,evensumQ,even6]
Relabel[even6,Compact]
Diagram[even6,ShowLabels->True]
-Graphics-
As another illustration, we will construct the poset of subsets of
{1,2,...,5} containing no two adjacent pairs. Every student of elementary
combinatorics knows that the number of such subsets equals a Fibonacci number.
nonadjQ[{___,x_,y_,___}] := False /; y == x+1;
nonadjQ[{___}] := True
Build[SubPoset[sub5,nonadjQ],non5]
RestoreSubPosetLabels[sub5,nonadjQ,non5]
Relabel[non5,Compact]
Diagram[non5,ShowLabels->True]
Building poset non5 ...
Done
-Graphics-
Card[non5]
13
Sure enough, it's a Fibonacci number!
Build[Dual[non5],non5dual]
RestoreDualPosetLabels[non5,non5dual]
Diagram[non5dual,ShowLabels->True]
Building poset non5dual ...
Done
-Graphics-
Build[Subsets[6],sub6]
Build[SubPoset[sub6,nonadjQ],non6]
Diagram[non6]
Building poset sub6 ...
Done
Building poset non6 ...
Done
-Graphics-
Card[non6]
21
Sure enough, another Fibonacci number. It's actually more interesting to look
at the dual poset. Here we use another special command RestoreDualPosetLabels
to put the labels back in the right places (otherwise they are generic).
Build[Dual[non6],non6dual]
RestoreDualPosetLabels[non6,non6dual]
Diagram[non6dual,ShowLabels->True]
Building poset non6dual ...
Done
-Graphics-
The cardinality of this poset (a Fibonacci number) can be further refined by
computing the rank generating function:
RGF[non6dual]
2 3
1 + 6 q + 10 q + 4 q
An easy combinatorial computation gets these coefficients directly, in terms
of Binomial coeffients:
n = 6;
Sum[Binomial[n-k+1,k]q^k, {k,0,n}]
2 3
1 + 6 q + 10 q + 4 q
INTERVAL SUB-POSETS
The interval sub-poset defined by elements A < B in P is the collection of all
elements X in P such that A ² X ² B. The command IntervalP[...,A,B] returns
the indices corresponding to such an interval. Then
Build[SubPoset[...,...],...] may be used to construct the poset.
We illustrate by constructing the interval in SetP[5] consisting of partitions
that lie between partitions A = {1,2,3,4,5} and B = {1,1,3,3,3}. Since A is
the bottom element of the poset, may also be described as the principal order
ideal generated by B.
Build[SetP[5],setp5]
Building poset setp5 ...
Done
indices = IntervalP[setp5,{1,2,3,4,5},{1,1,3,3,3}]
{1, 2, 9, 10, 11, 15, 16, 17, 36, 43}
Build[SubPoset[setp5,indices],subp5]
Building poset subp5 ...
Done
Diagram[subp5]
-Graphics-
Diagram[setp5,indices,Thinness->.8]
-Graphics-
LINEAR EXTENSIONS
A linear extension of a poset P with n elements is an order-preserving
bijection from P to an n-element chain. Since both P and the chain are
indexed by 1...n, we may represent such a map by a permutation of 1...n. The
command LinearExtensions[name] generates all linear extensions of P[name].
Each one is represented by a list in which index x appears in position k if
P[name][[x]] is mapped to the kth element of the chain. (Technically, this is
a topological sorting of P, i.e. a linear arrangement of the indices that
respects the order structure of P. The name "linear extension" usually refers
to the inverse permutation.)
To understand the output of LinearExtensions, one must appreciate that numbers
appearing in the list are indices, not labels. It can sometimes clarify things
to execute the command Relabel[name], after which labels and indices coincide.
A simple example should illustrate these remarks.
Build[ZigZag[4],zz4]
Diagram[zz4,ShowLabels->True]
Building poset zz4 ...
Done
-Graphics-
These are the original labels generated by the ZigZag command. If apply
Relabel and display again, the resulting labels show exactly how the elements
of P are indexed. Then we can verify that LinearExtensions produces
order-compatible arrangements of those indices.
Relabel[zz4]
Diagram[zz4,ShowLabels->True]
-Graphics-
LinearExtensions[zz4]
{{2, 4, 1, 3}, {2, 1, 4, 3}, {2, 1, 3, 4}, {1, 2, 4, 3}, {1, 2, 3, 4}}
Now a more complicated case:
Build[
OS[OS[OS[Antichain[2],Chain[1]],ZigZag[5]],Chain[2]],posetx]
Building poset posetx ...
Done
Diagram[posetx,ShowLabels->True]
-Graphics-
LinearExtensions[posetx] // Length
32
So there are 32 linear extensions of this poset.
P-PARTITIONS; ORDER POLYNOMIALS
Several interesting combinatorial invariants of a poset may be constructed
easily, once the linear extensions have been computed. For more mathematical
details about these constructions, the reader is referred to Stanley's
Enumerative Combinatorics .
A P-partition is an order-preserving map from P to the positive integers. It
is standard to introduce a generating function G[P,q] which enumerates
P-partitions according to their part sums. It can be shown that G[P,q] is a
rational function whose numerator enumerates linear extensions by major index.
(The major index of a permutation is the sum of the indices of its decents.)
Build[DS[Chain[2],Chain[2]],twochains]
Diagram[twochains,ShowLabels->True]
Building poset twochains ...
Done
-Graphics-
G[twochains,q]
2 3 4
1 + q + 2 q + q + q
----------------------------------
2 3 4
(1 - q) (1 - q ) (1 - q ) (1 - q )
Observe that there are six linear extensions whose major index is distributed
according to the numerator of the expression just computed:
LinearExtensions[twochains]
{{2, 4, 1, 3}, {2, 1, 4, 3}, {2, 1, 3, 4}, {1, 3, 2, 4},
{1, 2, 4, 3}, {1, 2, 3, 4}}
Map[MAJ,%]
{2, 4, 1, 2, 3, 0}
The "order polynomial" of a poset P counts order-preserving maps from P into
an n-element chain. It also has a rational generating function, in which the
numerator enumerates linear extensions by "descents".
OmegaGF[twochains,q]
2 3
q + 4 q + q
-------------
5
(1 - q)
Again we can see that the numerator shows the distribution of linear
extensions by number of descents:
Map[DES,LinearExtensions[twochains]]
{1, 2, 1, 1, 1, 0}
The order polynomial itself turns out in this case to be:
Omega[twochains,n] // Factor
441
MAXIMUM-SIZED ANTICHAINS; MINIMUM CHAIN COVERS.
The command MaxAntichain[P] returns the indices of a maximum-sized antichain
in P, and simultaneously computes the links in a minimum-sized covering of P
by chains. This information is stored in DilworthCover[P] (after the
celebrated theorem of Dilworth, which states that the cardinalities of these
two objects are the same).
Build[Subsets[3],sub3]
Relabel[sub3]
Diagram[sub3,MaxAntichain[sub3],DilworthCover[sub3],
ShowLabels->True]
Building poset sub3 ...
Done
-Graphics-
MaxAntichain[sub3]
{5, 6, 7}
DilworthCover[sub3]
{{1, 2}, {2, 5}, {3, 7}, {4, 6}, {7, 8}}
And a more complicated example:
MaxAntichain[y52211]
{19, 20, 21, 22, 23, 24, 25, 26, 27}
We can highlight these objects in the diagram:
Diagram[y52211,MaxAntichain[y52211],DilworthCover[y52211]]
-Graphics-