Differential poset

Last updated March 20, 2022

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 = r I (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 Young-Fibonacci graph, the Hasse diagram of the Young-Fibonacci lattice. Young-Fibonacci.svg — 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 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, while 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 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 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 that arise by taking products of the Young–Fibonacci lattices and Young's lattice.

Unsolved problem in mathematics:

Are there any differential lattices that are not products of Young's lattice and the Young–Fibonacci lattices?

(more unsolved problems in mathematics)

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 conjectured in Stanley (1988) that if P is a differential poset with $r n$ vertices at rank n, then

p(n)\leq r_{n}\leq F_{n},

where p(n) is the number of integer partitions of n and $F n$ is the nth 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 proved in Byrnes (2012), while the lower bound remains open. Stanley & Zanello (2012) proved an asymptotic version of the lower bound, showing that

r_{n}\gg n^{a}\exp(2{\sqrt {n}})

for every differential poset and some constant a. By comparison, the partition function has asymptotics

p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right).

All known bounds on rank sizes of differential posets are quickly growing functions. In the original paper of Stanley, it was shown (using eigenvalues of the operator DU) that the rank sizes are weakly increasing. However, it took 25 years before Miller (2013) showed that the rank sizes of an r-differential poset strictly increase (except trivially between ranks 0 and 1 when r = 1).

Properties

Every differential poset P shares a large number of combinatorial properties. A few of these include:

The number of paths of length 2n in the Hasse diagram of P beginning and ending at the minimal element is $(2 n - 1)!!$ , where $m!!$ is the double factorial function. In an r-differential poset, the number of such paths is $(2 n - 1)!! r n$ .^[1]
The number of paths of length 2n 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 $n!$ . In an r-differential poset, the number is $n! r n$ .^[2]
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 involutions in the symmetric group on n letters. In an r-differential poset, the sequence of these numbers has exponential generating function $e rx + x 2 /2$ .^[3]

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 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 symmetric groups, and are connected to the ring of symmetric functions; Okada (1994) defined algebras whose representation is encoded instead by the Young–Fibonacci lattice, and allow for analogous constructions such as a Fibonacci version of symmetric functions. It is not known whether similar algebras exist for every differential poset.^{[ citation needed ]} In another direction, Lam & Shimozono (2009) defined dual graded graphs corresponding to any Kac–Moody algebra.

Other variations are possible; Stanley (1990) defined versions in which the number r in the definition varies from rank to rank, while Lam (2008) defined a signed analogue of differential posets in which cover relations may be assigned a "weight" of −1.

Related Research Articles

In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. For example, 4 can be partitioned in five distinct ways:

In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for every locally finite partially ordered set and commutative ring with unity. Subalgebras called reduced incidence algebras give a natural construction of various types of generating functions used in combinatorics and number theory.

In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy, they are named after Eric Temple Bell, who wrote about them in the 1930s.

In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection. Indeed, these lattices of sets describe the scenery completely: every distributive lattice is—up to isomorphism—given as such a lattice of sets.

A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum and a unique infimum. An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor.

In mathematical order theory, an ideal is a special subset of a partially ordered set (poset). Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion. Ideals are of great importance for many constructions in order and lattice theory.

In geometry and combinatorics, an arrangement of hyperplanes is an arrangement of a finite set A of hyperplanes in a linear, affine, or projective space S. Questions about a hyperplane arrangement A generally concern geometrical, topological, or other properties of the complement, M(A), which is the set that remains when the hyperplanes are removed from the whole space. One may ask how these properties are related to the arrangement and its intersection semilattice. The intersection semilattice of A, written L(A), is the set of all subspaces that are obtained by intersecting some of the hyperplanes; among these subspaces are S itself, all the individual hyperplanes, all intersections of pairs of hyperplanes, etc.. These intersection subspaces of A are also called the flats ofA. The intersection semilattice L(A) is partially ordered by reverse inclusion.

In mathematics, in the branch of combinatorics, a graded poset is a partially ordered set (poset) P equipped with a rank functionρ from P to the set N of all natural numbers. ρ must satisfy the following two properties:

Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra.

In mathematics, Young's lattice is a lattice that is formed by all integer partitions. It is named after Alfred Young, who, in a series of papers On quantitative substitutional analysis, developed the representation theory of the symmetric group. In Young's theory, the objects now called Young diagrams and the partial order on them played a key, even decisive, role. Young's lattice prominently figures in algebraic combinatorics, forming the simplest example of a differential poset in the sense of Stanley (1988). It is also closely connected with the crystal bases for affine Lie algebras.

The mathematical field of combinatorics was studied to varying degrees in numerous ancient societies. Its study in Europe dates to the work of Leonardo Fibonacci in the 13th century AD, which introduced Arabian and Indian ideas to the continent. It has continued to be studied in the modern era.

The Fibonacci cubes or Fibonacci networks are a family of undirected graphs with rich recursive properties derived from its origin in number theory. Mathematically they are similar to the hypercube graphs, but with a Fibonacci number of vertices. Fibonacci cubes were first explicitly defined in Hsu (1993) in the context of interconnection topologies for connecting parallel or distributed systems. They have also been applied in chemical graph theory.

In mathematics, a fence, also called a zigzag poset, is a partially ordered set in which the order relations form a path with alternating orientations:

In mathematics, the Young–Fibonacci graph and Young–Fibonacci lattice, named after Alfred Young and Leonardo Fibonacci, are two closely related structures involving sequences of the digits 1 and 2. Any digit sequence of this type can be assigned a rank, the sum of its digits: for instance, the rank of 11212 is 1 + 1 + 2 + 1 + 2 = 7. As was already known in ancient India, the number of sequences with a given rank is a Fibonacci number. The Young–Fibonacci lattice is an infinite modular lattice having these digit sequences as its elements, compatible with this rank structure. The Young–Fibonacci graph is the graph of this lattice, and has a vertex for each digit sequence. As the graph of a modular lattice, it is a modular graph.

In geometry and polyhedral combinatorics, an integral polytope is a convex polytope whose vertices all have integer Cartesian coordinates. That is, it is a polytope that equals the convex hull of its integer points. Integral polytopes are also called lattice polytopes or Z-polytopes. The special cases of two- and three-dimensional integral polytopes may be called polygons or polyhedra instead of polytopes, respectively.

In combinatorial mathematics, an Eulerian poset is a graded poset in which every nontrivial interval has the same number of elements of even rank as of odd rank. An Eulerian poset which is a lattice is an Eulerian lattice. These objects are named after Leonhard Euler. Eulerian lattices generalize face lattices of convex polytopes and much recent research has been devoted to extending known results from polyhedral combinatorics, such as various restrictions on f-vectors of convex simplicial polytopes, to this more general setting.

In algebra and in particular in algebraic combinatorics, a quasisymmetric function is any element in the ring of quasisymmetric functions which is in turn a subring of the formal power series ring with a countable number of variables. This ring generalizes the ring of symmetric functions. This ring can be realized as a specific limit of the rings of quasisymmetric polynomials in n variables, as n goes to infinity. This ring serves as universal structure in which relations between quasisymmetric polynomials can be expressed in a way independent of the number n of variables.

This glossary of areas of mathematics is a list of sub-discliplines within pure and applied mathematics. Some entries are broad topics, like algebra, while others are narrower in scope, like convex geometry.

The order polynomial is a polynomial studied in mathematics, in particular in algebraic graph theory and algebraic combinatorics. The order polynomial counts the number of order-preserving maps from a poset to a chain of length $. These order-preserving maps were first introduced by Richard P. Stanley while studying ordered structures and partitions as a Ph.D. student at Harvard University in 1971 under the guidance of Gian-Carlo Rota.$

The affine symmetric groups are a family of mathematical structures that describe the symmetries of the number line and the regular triangular tiling of the plane, as well as related higher-dimensional objects. Each one is an infinite extension of a finite symmetric group, the group of permutations (rearrangements) of a finite set. In addition to their geometric description, the affine symmetric groups may be defined as collections of permutations of the integers that are periodic in a certain sense, or in purely algebraic terms as a group with certain generators and relations. They are studied as part of the fields of combinatorics and representation theory.

References

↑ Richard Stanley, Enumerative Combinatorics, Volume 1 (second edition). Cambridge University Press, 2011. , version of 15 July 2011. Theorem 3.21.7, page 384.
↑ Richard Stanley, Enumerative Combinatorics, Volume 1 (second edition). Cambridge University Press, 2011. , version of 15 July 2011. Theorem 3.21.8, page 385.
↑ Richard Stanley, Enumerative Combinatorics, Volume 1 (second edition). Cambridge University Press, 2011. , version of 15 July 2011. Theorem 3.21.10, page 386.

Byrnes, Patrick (2012), Structural Aspects of Differential Posets, ISBN 9781267855169 (UMN Ph.D. Thesis)
Fomin, Sergey (1994), "Duality of graded graphs", Journal of Algebraic Combinatorics, 3 (4): 357–404, doi: 10.1023/A:1022412010826
Lam, Thomas (2008), "Signed differential posets and sign-imbalance", Journal of Combinatorial Theory, Series A, 115 (3): 466–484, arXiv: math/0611296 , doi:10.1016/j.jcta.2007.07.003, S2CID 10802016
Lam, Thomas F.; Shimozono, Mark (2007), "Dual graded graphs for Kac-Moody algebras", Algebra & Number Theory, 1 (4): 451–488, arXiv: math/0702090 , doi:10.2140/ant.2007.1.451, S2CID 18253442
Lewis, Joel Brewster (2007), On Differential Posets (PDF) (Harvard College undergraduate thesis)
Miller, Alexander (2013), "Differential posets have strict rank growth: a conjecture of Stanley", Order, 30 (2): 657–662, arXiv: 1202.3006 , doi:10.1007/s11083-012-9268-y, S2CID 38737147 arXiv:1202.3006 [math.CO]
Okada, Soichi (1994), "Algebras associated to the Young-Fibonacci lattice", Transactions of the American Mathematical Society, American Mathematical Society, 346 (2): 549–568, doi: 10.2307/2154860 , JSTOR 2154860
Stanley, Richard P. (1988), "Differential posets", Journal of the American Mathematical Society, American Mathematical Society, 1 (4): 919–961, doi: 10.2307/1990995 , JSTOR 1990995
Stanley, Richard P. (1990), "Variations on differential posets", Invariant theory and tableaux (Minneapolis, MN), 1988, IMA Vol. Math. Appl., vol. 19, Springer, pp. 145–165
Stanley, Richard P.; Zanello, Fabrizio (2012), "On the Rank Function of a Differential Poset", Electronic Journal of Combinatorics, 19 (2): P13, doi: 10.37236/2258 , S2CID 7405057

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Richard Stanley, Enumerative Combinatorics, Volume 1 (second edition). Cambridge University Press, 2011. , version of 15 July 2011. Theorem 3.21.7, page 384.

[2] Richard Stanley, Enumerative Combinatorics, Volume 1 (second edition). Cambridge University Press, 2011. , version of 15 July 2011. Theorem 3.21.8, page 385.

[3] Richard Stanley, Enumerative Combinatorics, Volume 1 (second edition). Cambridge University Press, 2011. , version of 15 July 2011. Theorem 3.21.10, page 386.

[1]

[2]

[3]