6. More Illustrations and Applications
THE "POSET CONJECTURE"
Recall that OmegaGF[P,q] is the rational generating function for the order
polynomial of P.
Conjecture: For any poset P, the numerator of OmegaGF[p,q] has only real
roots, and they are all negative.
This is known as the Stanley-Neggers Conjecture, or sometimes just the Poset
Conjecture. It has been open for some time. We'll test it on three random
posets with 8 elements.
Build[RandomP[8,.5],testposet];
Diagram[testposet];
num=Numerator[OmegaGF[testposet,q]];
NRoots[num==0,q]
Building poset testposet ...
Done
q == -1.93653 || q == -0.582351 || q == -0.147788 || q == 0.
Build[RandomP[8,.5],testposet];
Diagram[testposet];
num=Numerator[OmegaGF[testposet,q]];
NRoots[num==0,q]
Building poset testposet ...
q == -4.08773 || q == -1.46493 || q == -0.372656 ||
q == -0.0746865
Build[RandomP[8,.3],testposet];
Diagram[testposet];
num=Numerator[OmegaGF[testposet,q]];
NRoots[num==0,q]
q == -2.46089 || q == -0.458551 || q == -0.0805616
THE "DISTRIBUTIVE LATTICE CONJECTURE"
Let P be a poset with 0 and 1. Let ci(P) be the number of chains of length i
from 0 to 1 in P (so,
in particular, c0(P)=0 and c1(P)=1). Define the chain polynomial of P by
C(P;q) = ·i ³ 1 ci(P) qi .
Conjecture: Let L be a distributive lattice. Then the polynomial C(L;q) has
only real zeros.
This has come to be known as the Distributive Lattice Conjecture. As a matter
of fact, it is equivalent to the "Poset Conjecture" described in the previous
section. The reason is that L = J(P) for some poset P, and it turns out that
C(P;q) is related to OmegaGF(P;q) by a simple change of variables. We will
illustrate this by computing both expressions for some randomly generated
posets.
We can calculate C(P;q) using the "ChainsBetweenGF" command:
Build[RandomP[5,.3],rand5]
Diagram[rand5]
Build[JofP[rand5],jprand5]
Diagram[jprand5]
chainpoly=ChainsBetweenGF[jprand5,1,Card[jprand5]]
Building poset rand5 ...
Done
Building poset jprand5 ...
Done
-Graphics-
-Graphics-
2 3 4 5
q + 14 q + 48 q + 60 q + 25 q
nn=Numerator[OmegaGF[rand5,q]]
2 3 4
q + 10 q + 12 q + 2 q
((nn/. q->t/(1+t)) (1+t)^5 ) //Together//Expand
2 3 4 5
t + 14 t + 48 t + 60 t + 25 t
NRoots[chainpoly==0,q]
q == -1. || q == -0.834017 || q == -0.462222 || q == -0.103761 ||
q == 0.
Build[RandomP[7,.5],rand7]
Diagram[rand7]
Build[JofP[rand7],jprand7]
chainpoly=ChainsBetweenGF[jprand7,1,Card[jprand7]]
Building poset rand7 ...
Done
Building poset jprand7 ...
Done
-Graphics-
2 3 4 5 6 7
q + 20 q + 116 q + 302 q + 397 q + 258 q + 66 q
Diagram[jprand7]
-Graphics-
NRoots[chainpoly==0,q]
q == -1. || q == -1. || q == -0.873398 || q == -0.589815 ||
q == -0.36538 || q == -0.0804976 || q == 0.
CASE STUDY: ZIG-ZAG POSETS
We conclude with an extended exploration of properties of a family of posets
called (for obvious reasons) "zigzag posets". Some of the observations made
here are new results, and were discovered empirically using this package.
Build[ZigZag[6],zz6]
Diagram[zz6,ShowLabels->True]
Building poset zz6 ...
Done
-Graphics-
First we investigate the lattice of order ideals of P[zz6]:
Build[JofP[zz6],jofzz6]
Diagram[jofzz6]
Building poset jofzz6 ...
Done
-Graphics-
RGF[jofzz6]
2 3 4 5 6
1 + 3 q + 4 q + 5 q + 4 q + 3 q + q
A study of the roots of these polynomials led us to conjecture and prove (with
Michelle Thompson) an explicit formula for the rank generating function. It
can be expressed neatly in terms of Chebyshev polynomials:
q^3 ChebyshevU[3,(q + 1 + 1/q)/2 ] // Expand
2 3 4 5 6
1 + 3 q + 4 q + 5 q + 4 q + 3 q + q
Next we investigate the linear extensions of P[zz5].
Build[ZigZag[5],zz5]
Diagram[zz5,ShowLabels->True]
Building poset zz5 ...
Done
-Graphics-
LinearExtensions[zz5]
{{3, 2, 5, 1, 4}, {3, 2, 1, 5, 4}, {3, 2, 1, 4, 5}, {2, 3, 5, 1, 4},
{2, 3, 1, 5, 4}, {2, 3, 1, 4, 5}, {2, 1, 4, 3, 5}, {2, 1, 3, 5, 4},
{2, 1, 3, 4, 5}, {3, 1, 2, 5, 4}, {3, 1, 2, 4, 5}, {1, 3, 2, 5, 4},
{1, 3, 2, 4, 5}, {1, 2, 4, 3, 5}, {1, 2, 3, 5, 4}, {1, 2, 3, 4, 5}}
The last result may be confusing, because (as noted earlier), the linear
extensions are represented by indices in P[zz5], not labels. We could relabel
the poset to make this clearer, but it turns out the original labels are
important for what follows. Instead we will re-display the linear extensions
so that labels are used rather than indices.
P[zz5]
{1, 3, 5, 2, 4}
lextzz5 = LinearExtensions[zz5] /.{1->1,2->3,3->5,4->2,5->4}
{{5, 3, 4, 1, 2}, {5, 3, 1, 4, 2}, {5, 3, 1, 2, 4}, {3, 5, 4, 1, 2},
{3, 5, 1, 4, 2}, {3, 5, 1, 2, 4}, {3, 1, 2, 5, 4}, {3, 1, 5, 4, 2},
{3, 1, 5, 2, 4}, {5, 1, 3, 4, 2}, {5, 1, 3, 2, 4}, {1, 5, 3, 4, 2},
{1, 5, 3, 2, 4}, {1, 3, 2, 5, 4}, {1, 3, 5, 4, 2}, {1, 3, 5, 2, 4}}
Now the permutations should "look" more like linear extensions, although,
technically, they are "topological sortings" of P[zz5], not linear extensions.
If we apply the function InversePermutation, we get the usual linear
extensions (i.e. order-preserving maps from P[zz5] to a 5-element chain). For
zigzag posets, these are in one-to-one correspondence with alternating
permutations of {1,2,3,4,5}, that is, permutations having the pattern a > b <
c > d < e ... .
alt5 = Map[InversePermutation,lextzz5]
{{4, 5, 2, 3, 1}, {3, 5, 2, 4, 1}, {3, 4, 2, 5, 1}, {4, 5, 1, 3, 2},
{3, 5, 1, 4, 2}, {3, 4, 1, 5, 2}, {2, 3, 1, 5, 4}, {2, 5, 1, 4, 3},
{2, 4, 1, 5, 3}, {2, 5, 3, 4, 1}, {2, 4, 3, 5, 1}, {1, 5, 3, 4, 2},
{1, 4, 3, 5, 2}, {1, 3, 2, 5, 4}, {1, 5, 2, 4, 3}, {1, 4, 2, 5, 3}}
Our permutations are now truly "alternating". A famous result of D. Andre
states that alternating permutations are enumerated by the Eulerian numbers.
These are the number whose exponential generating function is Tan[x] + Sec[x]
. Thus for example, for n=5, we have
LinearExtensions[zz5] // Length
16
D[Tan[x]+Sec[x],{x,5}] /. x->0
16
The subposet of WeakS[5] consisting of the topological sortings (our lextzz5)
has some interesting properties. First let's display it.
To find indices for permutations in alt5, we use the command LocateSet.
Build[WeakS[5],weaks5]
indices = LocateSet[weaks5,lextzz5]
Diagram[weaks5,indices,Thinness->.8]
Building poset weaks5 ...
Done
{11, 22, 25, 41, 44, 45, 63, 64, 67, 68, 85, 86, 89, 102, 103, 114}
-Graphics-
One can check that this subposet is actually an "interval" in P[weaks5]. In
other words, it consists of all elements lying between two fixed elements.
This is sometimes difficult to verify visually; the following test can be used
to be absolutely sure:
indices == IntervalP[weaks5,P[weaks5][[11]],P[weaks5][[114]]]
True
This fact follows from a more general result due to Bjorner and Wachs
("Permutation statistics and linear extensions of posets", Jour. Combinatorial
Theory A 57 (1991)).
Next we extract the sub-poset and take a good look at it.
Build[SubPoset[weaks5,indices],interval5]
RestoreSubPosetLabels[weaks5,indices,interval5]
Relabel[interval5,Compact]
Diagram[interval5,ShowLabels->True]
Building poset interval5 ...
Done
-Graphics-
The number of maximal chains from the bottom element to each element of P is
computed next.
MaximalChainsDown[interval5]
{1, 1, 1, 2, 1, 1, 3, 2, 2, 1, 5, 3, 3, 5, 11, 16}
We noticed that the number (16) of maximal chains from bottom to top in
P[alt5subposet] was equal to the number of maximal chains from bottom to top
in P[weaks4], a poset with very different structure.
Build[WeakS[4],weaks4]
Diagram[weaks4]
Building poset weaks4 ...
Done
-Graphics-
MaximalChainsDown[weaks4]
{1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 2, 2, 1, 3, 3, 3, 2, 3, 5, 6, 5,
16}
It turns out to be a theorem that, in general, the number of maximal chains in
these two posets is the same. However, we know of no simple proof of this
result.