Content deleted Content added
m fix link |
m custom spacing in math formulas (via WP:JWB) |
||
| (14 intermediate revisions by 7 users not shown) | |||
Line 3:
==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 poset|graded]] and [[locally finite poset|locally finite]] with a unique minimal element;
* for every two distinct elements ''x'', ''y'' of ''P'', the number of elements [[covering relation|covering]] both ''x'' and ''y'' is the same as the number of elements covered by both ''x'' and ''y''; and
Line 10:
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 algebra]]ic setting: taking the elements of the poset ''P'' to be formal [[basis (linear algebra)|basis]] vectors of an (infinite
This latter reformulation makes a differential poset into a combinatorial realization of a [[Weyl algebra]], and in particular explains the name ''differential'': the operators "[[derivative|''d''/''dx'']]" and "multiplication by ''x''" on the vector space of
==Examples==
[[File:Young-Fibonacci.svg|thumb|300px|The [[Young–Fibonacci graph]], the [[Hasse diagram]] of the Young–Fibonacci lattice.]]
The canonical examples of differential posets are [[Young's lattice]], the poset of [[integer partition]]s ordered by inclusion, and the [[Young–Fibonacci lattice]]. Stanley's initial paper established that Young's lattice is the only {{nowrap|1-differential}} [[distributive lattice]],
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. {{harvtxt|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 {{harvtxt|Lewis|2007}}, where it is shown that there are [[uncountable set|uncountably]] many {{nowrap|1-differential posets}}. On the other hand, explicit examples of differential posets are rare; {{harvtxt|Lewis|2007}} gives a convoluted 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 {{nowrap|''r''-differential}} and {{nowrap|''s''-differential}} poset is always an (''r'' +&
{{unsolved|mathematics|Are there any differential lattices that are not products of Young's lattice and the Young–Fibonacci lattices?}}
==Rank growth==
In addition to the question of whether there are other differential lattices, there are several long-standing open problems relating to the rank growth of differential posets. It was
: <math>
where ''p''(''n'') is the [[partition function (number theory)|number of integer partitions]] of ''n'' and {{math|''F''<sub>''n''</sub>}} is the ''n''th [[Fibonacci number]]. In other words, the conjecture states that at every rank, every differential poset has a number of vertices lying between the numbers for Young's lattice and the Young-Fibonacci lattice. The upper bound was [[mathematical proof|proved]] in {{harvtxt|Byrnes|2012}}
: <math> r_n \gg n^a \exp(2\sqrt{n}) </math>
for every differential poset and some constant ''a''. By comparison, the partition function has asymptotics
: <math> p(n) \sim \frac{1}{4n\sqrt{3}} \exp\left({\pi \sqrt {\frac{2n}{3}}}\right).</math>
All known bounds on rank sizes of differential posets are quickly growing functions. In the original paper of Stanley, it was shown (using [[eigenvalue]]s of the operator ''DU'') that the rank sizes are weakly increasing. However, it took 25 years before {{harvtxt|Miller|2013}} showed that the rank sizes of an {{nowrap|''r''-differential}} poset strictly increase (except trivially between ranks 0 and 1 when ''r''
==Properties==
[[File:Young's lattice.svg|thumb|300px|A
Every differential poset ''P'' shares a large number of combinatorial properties. A few of these include:
* The number of paths of length 2''n'' in the Hasse diagram of ''P'' beginning and ending at the minimal element is {{math|(2''n'' − 1)!!}},
* The number of paths of length 2''n'' in the Hasse diagram 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 {{math|''n''!}}. In an {{nowrap|''r''-differential}} poset, the number is {{math|''n''!
* The number of upward paths of length ''n'' in the Hasse diagram of ''P'' beginning with the minimal element is equal to the number of [[involution (mathematics)|involutions]] in the [[symmetric group]] on ''n'' letters. In an {{nowrap|''r''-differential}} poset, the sequence of these numbers has [[exponential generating function]] {{math|''e''<sup>{{hairsp}}''rx'' + ''x''<sup>2</sup>/2</sup>}}.
==Generalizations==
In a differential poset, the same set of edges is used to compute the up and down operators ''U'' and ''D''. If one permits different sets of up edges and down edges (sharing the same vertex sets, and satisfying the same relation), the resulting concept is the ''dual graded graph'', initially defined by {{harvtxt|Fomin|1994}}. One recovers differential posets as the case that the two sets of edges coincide.
Much of the interest in differential posets is inspired by their connections to [[representation theory]]. The elements of Young's lattice are integer partitions, which encode the [[representations of the
Other variations are possible; {{harvtxt|Stanley|1990}} defined versions in which the number ''r'' in the definition varies from rank to rank, while {{harvtxt|Lam|2008}} defined a signed analogue of differential posets in which cover relations may be assigned a "weight" of −1.
Line 52:
==References==
{{Reflist}}
== Sources ==
* {{citation |last=Stanley |first=Richard |year=2011 |title=Enumerative Combinatorics |edition=2 |volume=1 |url=http://www-math.mit.edu/~rstan/ec/ec1.pdf |access-date=2015-09-21 |archive-date=2011-05-31 |archive-url=https://web.archive.org/web/20110531113533/http://www-math.mit.edu/~rstan/ec/ec1.pdf |url-status=dead }}
* {{citation |last=Byrnes |first=Patrick |title=Structural Aspects of Differential Posets |year=2012 |isbn=9781267855169}}
* {{citation |last=Fomin |first=Sergey |author-link=Sergey Fomin |title=Duality of graded graphs |journal=Journal of Algebraic Combinatorics |volume=3 |year=1994 |issue=4 |pages=357–404 |doi=10.1023/A:1022412010826 |doi-access=free}}
* {{citation |last1=Lam |first1=Thomas F. |title=Signed differential posets and sign-imbalance |journal=Journal of Combinatorial Theory, Series A |volume=115 |issue=3 |year=2008 |pages=466–484 |doi=10.1016/j.jcta.2007.07.003 |arxiv=math/0611296 |s2cid=10802016}}
* {{citation |last1=Lam |first1=Thomas F. |last2=Shimozono |first2=Mark |title=Dual graded graphs for Kac-Moody algebras |journal=Algebra & Number Theory |volume=1 |year=2007 |issue=4 |pages=451–488 |doi=10.2140/ant.2007.1.451 |arxiv=math/0702090 |s2cid=18253442}}
* {{citation |last=Lewis |first=Joel Brewster |title=On Differential Posets |year=2007 |url=https://blogs.gwu.edu/jblewis/files/2018/04/JBLHarvardSeniorThesis-20drube.pdf}} ([[Harvard College]] undergraduate thesis)
* {{citation |last=Miller |first=Alexander |year=2013 |title=Differential posets have strict rank growth: a conjecture of Stanley |journal=Order |volume=30 |issue=2 |pages=657–662 |doi=10.1007/s11083-012-9268-y |arxiv=1202.3006 |s2cid=38737147}}
* {{citation |last=Okada |first=Soichi |title=Algebras associated to the Young-Fibonacci lattice |journal=Transactions of the American Mathematical Society |volume=346 |issue=2 |pages=549–568 |year=1994 |publisher=American Mathematical Society |doi=10.2307/2154860 |jstor=2154860 |doi-access=free}}
*{{citation |last=Stanley |first=Richard P. |author-link=Richard P. Stanley |title=Differential posets |journal=Journal of the American Mathematical Society |volume=1 |issue=4 |pages=919–961 |year=1988 |doi=10.2307/1990995 |jstor=1990995 |publisher=American Mathematical Society |doi-access=free}}
* {{citation |last=Stanley |first=Richard P. |author-link=Richard P. Stanley |chapter=Variations on differential posets |title=Invariant theory and tableaux (Minneapolis, MN), 1988 |series=IMA Vol. Math. Appl. |volume=19 |pages=145–165 |publisher=Springer |year=1990}}
* {{citation |last1=Stanley |first1=Richard P. |author1-link=Richard P. Stanley |last2=Zanello |first2=Fabrizio |title=On the Rank Function of a Differential Poset |journal=Electronic Journal of Combinatorics |volume=19 |issue=2 |year=2012 |pages=P13 |doi=10.37236/2258 |s2cid=7405057 |url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p13 |doi-access=free|arxiv=1111.4371 }}
[[Category:Representation theory]]
| |||