Differential Posets

1. On the rank function of a differential poset - Stanley & Zanello http://arxiv.org/abs/1111.4371
2. Differential Posets - Stanley http://www.ams.org/journals/jams/1988-01-04/S0894-0347-1988-0941434-9/S0894-0347-1988-0941434-9.pdf
3. Variations on Differential Posets - Stanley http://math.mit.edu/~rstan/pubs/pubfiles/78.pdf
4. Differential Posets and Smith Normal Forms - Alexander Miller and Victor Reiner http://www.springerlink.com/content/qkv6115u374xw202/fulltext.pdf
5. Smith invariants of UD and DU linear operators in differential posets - A Miller http://math.umn.edu/~reiner/REU/DownUpReport2006.pdf
6. Patrick Byrnes (U. Minnesota) proved an upper bound of the rank function.
7. Fibonacci Lattice - Stanley http://www.fq.math.ca/Scanned/13-3/stanley.pdf
8. Young's lattice and Dihedral Symmetries - Ruedi Suter http://pdn.sciencedirect.com/science?_ob=MiamiImageURL&_cid=272420&_user=501045&_pii=S0195669801905414&_check=y&_origin=article&_zone=toolbar&_coverDate=28-Feb-2002&view=c&originContentFamily=serial&wchp=dGLbVlS-zSkWb&md5=c2d8fa3a72beb7818df9d40550c9a380/1-s2.0-S0195669801905414-main.pdf
9. Algebras associated to the Young-Fibonacci lattice - S Okada http://www.ams.org/journals/tran/1994-346-02/S0002-9947-1994-1273538-7/S0002-9947-1994-1273538-7.pdf
10. The automorphism group of the Fibonacci poset: a “not too difficult” problem of Stanley from 1988 - JD Farley & S Kim http://www.springerlink.com/index/R81P4R9620432166.pdf

Questions

• [SOLVED] For any differential poset, it's rank function $p_n$ is strictly increasing, $p_n < p_{n+1}$. http://arxiv.org/pdf/1202.3006v1
• The minimal $p_i$'s for $r$-differential posets are achieved by the Young's lattice $Y^r$.
• P. Byrnes proved that the only 1-differential lattices are Young's lattice and Fibonacci lattice. Classify $r$-differential lattices, for instance, for $r=2$.
• If $P$ is differential, is $J(P)$ differential? NO, The only differential & distributive lattices are $Y^r$.
• What can we say about the automorphism group of differential posets?
• Make a symmetric ftn out of differential posets?
• Make a polytope associated to differential posets?
• suppose one can replace a crown with a cap (or a cap with a crown) in a natural way. classify equivalence classes for this kind of exchanges.
• What is the number of 1-differential (or $r$-differential) posets up to rank k?
• Dihedral Symmetry for Fibonacci lattices?
• Does a differential poset determined uniquely by the sequence of "down numbers" $(d(x))_{x\in P_i}$ (or even by its rank function)?

Intermediate Posets between Young lattice and Fibonacci lattice(?)

• Generating function for partition function: $1/(1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} + \cdots)$
  • = 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, 31185, 37338, 44583, 53174, 63261, 75175, 89134
• Generating function for Fibonacci numbers: $1/(1 - x - x^2)$
  • = 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169
• Are there posets whose rank functions have generating functions:
  • $1/(1 - x - x^2 + x^5 + x^7)$ $= 1 + x + 2 x^2+3 x^3+5 x^4+7 x^5+11 x^6+15 x^7+22 x^8+30 x^9+42 x^10+56 x^11 +76 x^12 +99 x^13 + 130 x^14+165 x^15+209 x^16+256 x^17+310 x^18+360 x^19+406 x^20+427 x^21+412 x^22+320 x^23+116 x^24-280 x^25-951 x^26-2049 x^27-3747 x^28-6324 x^29-10111 x^30+O(x^31)$
  • THIS IS NOT POSITIVE
  • $1/(1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15})$ $= 1+x+2 x^2+3 x^3+5 x^4+7 x^5+11 x^6+15 x^7+22 x^8+30 x^9+42 x^10+56 x^11+77 x^12+101 x^13+135 x^14+176 x^15+231 x^16+297 x^17+385 x^18+490 x^19+627 x^20+792 x^21+1003 x^22+1257 x^23+1580 x^24+1968 x^25+2457 x^26+3048 x^27+3788 x^28+4685 x^29+5809 x^30+O(x^31)$
  • THIS IS POSITIVE. {1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1003, 1257, 1580, 1968, 2457, 3048, 3788, 4685, 5809, 7178, 8895, 11005, 13660, 16952, 21121, 26340, 32992, 41405, 52196, 65962, 83723, 106538, 136096, 174260, 223827, 288015, 371468, 479664, 620278, 802545, 1039084, 1345288, 1741821, 2254097, 2915767, 3768485, 4866784, 6278475, 8091602, 10415980, 13393293, 17200735, 22065816, 28273731, 36189458, 46271475, 59105273, 75427945, 96179633, 122546546, 156041060, 198575639, 252589047, 321172117, 408268469, 518886917, 659423394, 838017495, 1065072137}

Morphisms of Differential Posets

• Morphisms of differential posets shoule be:
  • rank-preserving
  • commutes with D(or U, or DU or UD) operator(?)

Ideas

• Count "crowns" and "caps". More caps generally results in more vertices.
  • Count the number of caps and crowns in each rank.
  • Give bounds to the maximal possible number of crowns(caps).
• $p(n) \sim \frac {1} {4n\sqrt{3}} e^{\pi \sqrt {\frac{2n}{3}}} \mbox { as } n\rightarrow \infty.$
• $F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} = \frac{\varphi^n-\psi^n}{\sqrt 5}$, where $\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\dots\,$ and $\psi = \frac{1 - \sqrt{5}}{2} = 1 - \varphi = - {1 \over \varphi}$.
• Look at adjacency matrix (Laplacian matrix) of the Hesse diagram of rank-selected poset $P_{[i-1,i]}$ (or $P_{[0,i]}$). Compute the determinant or eigenvalues using linear algebra and get a strict increase of rank function.

Generalizations

• Dual graded graphs. Fomin, S.: Duality of graded graphs. J. Algebr. Comb. 3, 357–404 (1994), Fomin, S.: Schensted algorithms for dual graded graphs. J. Algebr. Comb. 4, 5–45 (1995)

Other Facts about Differential Posets

• Differential $\Rightarrow$ modular
• Differential & distributive lattice $\Rightarrow$ Young's lattice (Stanley)
• Differential lattice & every complemented interval has length $\leq 2$ $\Rightarrow$ Fibonacci lattice $Z(r)$ (Stanley)

From Patrick Byrnes

• 3/5/2012

Taedong,

Short version: by "cycle" I mean "crown".

Longer version: I mean induced cycle instead of just cycle. I think what I want is a sequence a_1, ..., a_n such that:

each {a_i,a_{i+1}} is a subset of a hyperedge, and {a_i, a_{i+1}, a_{i+2}} is not a subset of a hyperedge (all of this is mod n).

With this definition it is easy to see that the Fibonacci differential posets are the only diffferential posets whose hypergraphs do not have induced cycles. This is because an induced cycle corresponds to a crown in the Hasse diagram. And, any differential poset without a crown must be a Fibonacci differential poset.

Pat

• 2/14/2012

Taedong,

Yes, I've tried to modify the upper bound proof to give a lower bound with no success.

"Replacing crowns with caps" does need to have a clearer definition. Generally, the interconnectedness does not allow for just replacing one crown with one cap. It seems to generally be that you need to toggle some set of caps/crowns to crowns/caps. I don't have details worked out yet. I am thinking though that you would only need to look at 2 successive ranks. I sometimes think looking at the hypergraph whose vertices are P_n and whose edges are the subsets of P_n that are all covered by a common element could be useful (or sometimes maybe look at the simplicial complex whose facets are the edges of the hypergraph instead). When considering this hypergraph crowns are a triangle that has each side as an edge in the hypergraph (but not the whole triangle) and caps are a triangle that is an edge of the hypergraph. The pictures of such hypergraphs look to alternate crowns and caps. Maybe toggling a certain subhypergraph would do the trick.

Also, I've now completed a draft for my thesis. I have attached a copy in case you are interested. I still need to do some editing, but I'm hoping it is largely done.

Incidentally, do you know where the term "cap" came from in this context?

Pat

• 1/26/2012

Taedong,

1. If you replace a crown with a cap (if that is possible) you will end up with 1 more vertex. The cap has 1 covering vertex, plus 3 more vertices (one singleton above each vertex). The crown has 3 covering vertices (that cover pairwise). This gets more complicated if you cannot replace a crown immediately with a cap, but the general principle that a crown results in 1 fewer vertex than a cap seems to hold true (well, up to some kind of linear dependence of crowns). Unfortunately, I don't have data for all that big of ranks. So, maybe something different happens when things reach some level of complication.

2. In Young's lattice every time you have a vertex with up degree 3 that means that in the Young diagram for the appropriate partition there are 3 boxes that you can add. You can add these boxes in any order. Thus, there is a copy of a binomial poset on 3 elements with root of the original vertex in question (with up degree 3). This also holds true by replacing 3 with any n you would like.

Pat

• 1/15/2012

Taedong,

I have looked into trying to prove that the rank sizes of differential posets are strictly increasing. However, I have not succeeded in finding a proof.

I can send you a copy of my thesis when I am done. I suspect I should at least have a completed draft in the next month or so (and maybe a finished copy).

The main results I have in my thesis are that the upper bound on the ranks of differential posets is given by the r-differential Fibonacci poset., that the only 1-differential lattices are Young's lattice and the 1-differential Fibonacci poset, and that the only underlying posets for quantized differential posets are the r-differential Fibonacci posets.

Pat

• 1/24/2012

Taedong,

I haven't gotten around to formally writing up my ideas about a way to approach the lower bound. I am going to do a quick write-up now.

Basically, it seems to me the real issue is dealing with "caps" and "crowns" (crowns being covering 3 mutually adjacent vertices with 3 vertices such that each of the covering vertices covers 2 of the 3 covered vertices, caps being covering 3 mutually adjacent vertices with one vertex voering all 3). Locally, a cap will result in one more vertex than a crown.

The Fibonacci differential poset has no crowns at all. This is one reason why it should be the biggest differential poset.

Young's lattice has a lot of crowns. The only caps are those immediately above crowns. I wonder if one could not use this property to show that Young's lattice has at least as many crowns as any other 1-differential poset at each level. My biggest concern here is that I fear the situation gets complicated for ranks that I do not have data for (where the adjacency graph of each rank gets more complicated). I suspect one might be better off considering dependencies amongst the crowns as well.

I'm not sure how much of this is well known. None of it seems real deep, but the upper bound proof is not very deep either.

Pat