Differential poset
In mathematics, a differential poset is a partially ordered set (or poset for short) satisfying certain local properties. (The formal definition is given below.) This family of posets was introduced by Stanley (1988) as a generalization of Young's lattice (the poset of integer partitions ordered by inclusion), many of whose combinatorial properties are shared by all differential posets. In addition to Young's lattice, the other most significant example of a differential poset is the Young-Fibonacci lattice.
Definitions
A poset P is said to be a differential poset, and in particular to be r-differential (where r is a positive integer), if it satisfies the following conditions:
- P is graded and locally finite with a unique minimal element;
- for every two distinct elements x, y of P, the number of elements covering both x and y is the same as the number of elements covered by both x and y; and
- for every element x of P, the number of elements covering x is exactly r more than the number of elements covered by x.
These basic properties may be restated in various ways. For example, Stanley shows that the number of elements covering two distinct elements x and y of a differential poset is always either 0 or 1, so the second defining property could be altered accordingly.
The defining properties may also be restated in the following linear algebraic setting: taking the elements of the poset P to be formal basis vectors of an (infinite dimensional) vector space, let D and U be the operators defined so that D x is equal to the sum of the elements covered by x, and U x is equal to the sum of the elements covering x. (The operators D and U are called the down and up operator, for obvious reasons.) Then the second and third conditions may be replaced by the statement that DU – UD = rI (where I is the identity).
This latter reformulation makes a differential poset into a combinatorial realization of a Weyl algebra, and in particular explains the name differential: the operators "d/dx" and "multiplication by x" on the vector space of polynomials obey the same commutation relation as U and D/r.
Examples
The canonical examples of differential posets are Young's lattice, the poset of integer partitions ordered by inclusion, and the Young-Fibonacci lattice. Stanley's initial paper established that Young's lattice is the only 1-differential distributive lattice, Byrnes (2012) showed that these are the only 1-differential lattices.
There is a canonical construction (called "reflection") of a differential poset given a finite poset that obeys all of the defining axioms below its top rank. (The Young-Fibonacci lattice is the poset that arises by applying this construction beginning with a single point.) This can be used to show that there are infinitely many differential posets. Stanley (1988) includes a remark that "[David] Wagner described a very general method for constructing differential posets which make it unlikely that [they can be classified]." This is made precise in Lewis (2007), where it is shown that there are uncountably many 1-differential posets. On the other hand, explicit examples of differential posets are rare; Lewis (2007) gives an explicit (but complicated and ugly) description of a differential poset other than the Young and Young-Fibonacci lattices.
The Young-Fibonacci lattice has a natural r-differential analogue for every positive integer r. These posets are lattices, and can be constructed by a variation of the reflection construction. In addition, the product of an r-differential and s-differential poset is always an (r + s)-differential poset. This construction also preserves the lattice property. It is not known for any r > 1 whether there are any r-differential lattices other than those than arise by taking products of the Young-Fibonacci lattices and Young's lattice.
History, significance, and open questions
![[icon]](/wiki/File:Wiki_letter_w_cropped.svg?lang=en){kind=small} | This section needs expansion. You can help by adding to it. (October 2013) |
Properties
| This section needs expansion. You can help by adding to it. (October 2013) |
Every differential poset P shares a large number of combinatorial properties. A few of these include:
- The number of paths of 2n + 1 elements of P beginning with the minimal element such that the first n steps are covering relations from a smaller to a larger element of P while the last n steps are covering relations from a larger to a smaller element of P is n!.
Generalizations
| This section needs expansion. You can help by adding to it. (October 2013) |
Lam (2008) defined a signed analogue of differential posets.
References
- Byrnes, Patrick (2012), Structural Aspects of Differential Posets, ISBN 9781267855169 (UMN Ph.D. Thesis)
- Lam, Thomas (2008), "Signed differential posets and sign-imbalance", Journal of Combinatorial Theory Series A, 115 (3): 466–484
- Lewis, Joel Brewster (2007), On Differential Posets [1] (Harvard College undergraduate thesis)
- Miller, Alexander (2012), Differential posets have strict rank growth: a conjecture of Stanley arXiv:1202.3006 [math.CO]
- Stanley, Richard P. (1988), "Differential posets", Journal of the American Mathematical Society, 1 (4), American Mathematical Society: 919–961, doi:10.2307/1990995, JSTOR 1990995
- Stanley first = Richard P. (1990), Variations on differential posets, IMA Vol. Math. Appl., vol. 19, Springer, pp. 145--165
{{citation}}: Missing pipe in:|last=(help); Unknown parameter|booktitle=ignored (help) - Stanley, Richard P.; Zanello, Fabrizio (2012), "On the Rank Function of a Differential Poset", Electronic Journal of Combinatorics, 19 (2): P13