×

zbMATH — the first resource for mathematics

Differential posets. (English) Zbl 0658.05006
The author has introduced a class of partially ordered sets, called differential posets, with many remarkable combinatorial and algebraic properties. The problem is concerned with counting of saturated chains, \(x_ 1<x_ 2<...<x_ k\) or of “Hasse walks” \(x_ 1,x_ 2,...,x_ k\) with either \(x_{i+1}\) covers \(x_ i\) or \(x_ i\) covers \(x_{i+1}\), \(1\leq i\leq k-1\) with various properties. A basic tool in the theory of differential posets P is the use of two adjoint linear transformations U and D of vector space of linear combinations of elements of P. If \(x\in P\) then \(Ux\) (respectively, \(Dx\)) is the sum of all elements covering \(x\) (respectively, which \(x\) covers). A fundamental property of \(U\) and \(D\) is the commutative rule \(DU-UD=rI\) for some positive integer r. Thus differential posets may be regarded as yielding a representation of the “Weyl algebra” generated by \(U\) and \(D/r\). The spectrum of the operator \(UD\) and its eigenvectors are computed and the result is extended to more general functions of \(U\) and \(D\). The spectrum of \(UD\) is closely related to the spectrum of the adjacency matrix of certain finite graphs associated with differential posets.
An example of a differential poset is Young’s lattice Y, first studied by G. Kreweras. It is defined as the set of all partitions of all nonnegative integers n ordered by inclusion of Young diagrams. Thus if \(\lambda =(\lambda_ 1\geq \lambda_ 2\geq...)\) and \(\mu =(\mu_ 1,\mu_ 2,...)\) are parititions, \((\lambda_ 1\geq \lambda_ 2\geq..\). and \(\mu_ 1\geq \mu_ 2\geq...)\), then \(\mu\leq \lambda\) in Y if and only if \(\mu_ i\leq \lambda_ i\) for all i. Young’s lattice is locally finite distributive lattice. In fact it is the lattice \(J_ f({\mathbb{N}}^ 2)\) of finite order ideals of the poset \({\mathbb{N}}^ 2\). If \(\lambda\in Y\) is a partition of n, it is indicated by \(| \lambda | =n\) or \(\lambda\vdash n\). Young’s lattice is graded with rank function \(\rho\) given by \(\rho(\lambda)=| \lambda |\). Many remarkable enumerative properties of Y are consequences of the theory of symmetric functions, the representation theory of the symmetric group, the complex general linear group, and the Robinson-Schensted correspondence. A standard Young tableau (SYT) of shape \(\lambda\) may be identified with a Saturated Chain \(\phi =\lambda^ 0\subset \lambda^ 1\subset...\subset \lambda^ n\) of partitions from \(\phi\) to \(\lambda\). If \(f^{\lambda}\) denotes the number SYT of shape \(\lambda\), then \(\sum_{\lambda \vdash n}(f^{\lambda})^ 2=n!\) asserts that the number of sequences (or Hasse walks) \(\phi =\lambda^ 0<\lambda^ 1<...<\lambda^ n>\mu^{n- 1}>...>\mu^ 0=\phi,\) where \(\lambda^ i\) and \(\mu^ i\) are partitions of i, is equal to \(n!\).
If P is a graded poset then \(\rho\) denotes its rank function, i.e., if \(x\in P\) then \(\rho(x)\) is the length \(\ell\) of the longest chain \(x_ 0<x_ 1<...<x_{\ell}=x\) in P with top element x. Write \(P_ i=\{x\in P:\quad \rho (x)=i\}\) so \(P=P_ 0\dot\cup P_ 1 \dot\cup...\) (disjoint union). The counting of chains in partially ordered sets is a well developed subject with many applications in enumerative combinatorics, probability theory and statistical mechanics besides other areas.
Reviewer: M.Cheema

MSC:
05A15 Exact enumeration problems, generating functions
06A06 Partial orders, general
05A17 Combinatorial aspects of partitions of integers
20C30 Representations of finite symmetric groups
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Mehdi Behzad, Gary Chartrand, and Linda Lesniak-Foster, Graphs & digraphs, PWS Publishers, Boston, Mass., 1979. · Zbl 0403.05027
[2] Allan Berele, A Schensted-type correspondence for the symplectic group, J. Combin. Theory Ser. A 43 (1986), no. 2, 320 – 328. · Zbl 0633.05009 · doi:10.1016/0097-3165(86)90070-1 · doi.org
[3] Garrett Birkhoff, Lattice theory, Third edition. American Mathematical Society Colloquium Publications, Vol. XXV, American Mathematical Society, Providence, R.I., 1967. · Zbl 0153.02501
[4] A. Bondy and U. S. R. Murty, Graph theory with applications, North-Holland, New York, 1976. · Zbl 1226.05083
[5] Lynne M. Butler, Rational generating functions for enumerating chains of partitions, J. Combin. Theory Ser. A 50 (1989), no. 1, 132 – 161. · Zbl 0663.05005 · doi:10.1016/0097-3165(89)90010-1 · doi.org
[6] Louis Comtet, Advanced combinatorics, Revised and enlarged edition, D. Reidel Publishing Co., Dordrecht, 1974. The art of finite and infinite expansions. · Zbl 0283.05001
[7] Dragoš M. Cvetković, Michael Doob, and Horst Sachs, Spectra of graphs, Pure and Applied Mathematics, vol. 87, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. Theory and application. · Zbl 0824.05046
[8] Paul H. Edelman, Abstract convexity and meet-distributive lattices, Combinatorics and ordered sets (Arcata, Calif., 1985) Contemp. Math., vol. 57, Amer. Math. Soc., Providence, RI, 1986, pp. 127 – 150. · doi:10.1090/conm/057/856235 · doi.org
[9] R. J. Glauber, Some notes on multiple-boson processes, Phys. Rev. 84 (1951), 395-400. · Zbl 0044.43603
[10] F. M. Goodman, P. de la Harpe, and V. Jones, Coxeter diagrams and towers of algebras, Chapter 2, Towers of multi-matrix algebras (preliminary version), MSRI book series, Springer, New York (to appear). · Zbl 0698.46050
[11] P. Hanlon and D. Wales, On the decomposition of Brauer’s centralizer algebras, J. Algebra (to appear). · Zbl 0695.20026
[12] G. Kreweras, Sur une classe de problèmes de dénombrement liés au trellis des partitions des entiers, Cahiers du BURO, vol. 6, 1965.
[13] Joseph P. S. Kung, Radon transforms in combinatorics and lattice theory, Combinatorics and ordered sets (Arcata, Calif., 1985) Contemp. Math., vol. 57, Amer. Math. Soc., Providence, RI, 1986, pp. 33 – 74. · doi:10.1090/conm/057/856232 · doi.org
[14] I. G. Macdonald, Symmetric functions and Hall polynomials, The Clarendon Press, Oxford University Press, New York, 1979. Oxford Mathematical Monographs. · Zbl 0487.20007
[15] Willard Miller Jr., Lie theory and special functions, Mathematics in Science and Engineering, Vol. 43, Academic Press, New York-London, 1968.
[16] Marvin Marcus and Henryk Minc, A survey of matrix theory and matrix inequalities, Allyn and Bacon, Inc., Boston, Mass., 1964. · Zbl 0247.15002
[17] Robert A. Proctor, Representations of \?\?(2,\?) on posets and the Sperner property, SIAM J. Algebraic Discrete Methods 3 (1982), no. 2, 275 – 280. · Zbl 0496.06004 · doi:10.1137/0603026 · doi.org
[18] Bruce E. Sagan and Richard P. Stanley, Robinson-Schensted algorithms for skew tableaux, J. Combin. Theory Ser. A 55 (1990), no. 2, 161 – 193. · Zbl 0732.05061 · doi:10.1016/0097-3165(90)90066-6 · doi.org
[19] Richard P. Stanley, Ordered structures and partitions, American Mathematical Society, Providence, R.I., 1972. Memoirs of the American Mathematical Society, No. 119. · Zbl 0246.05007
[20] Richard P. Stanley, Theory and application of plane partitions. I, II, Studies in Appl. Math. 50 (1971), 167 – 188; ibid. 50 (1971), 259 – 279. · Zbl 0225.05011
[21] Richard P. Stanley, The Fibonacci lattice, Fibonacci Quart. 13 (1975), no. 3, 215 – 232. · Zbl 0328.06007
[22] Richard P. Stanley, The stable behavior of some characters of \?\?(\?,\?), Linear and Multilinear Algebra 16 (1984), no. 1-4, 3 – 27. · Zbl 0573.20042 · doi:10.1080/03081088408817606 · doi.org
[23] Richard P. Stanley, Quotients of Peck posets, Order 1 (1984), no. 1, 29 – 34. · Zbl 0564.06002 · doi:10.1007/BF00396271 · doi.org
[24] -, Enumerative combinatorics, vol. I, Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986.
[25] Richard P. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM J. Algebraic Discrete Methods 1 (1980), no. 2, 168 – 184. · Zbl 0502.05004 · doi:10.1137/0601021 · doi.org
[26] Richard P. Stanley, Variations on differential posets, Invariant theory and tableaux (Minneapolis, MN, 1988) IMA Vol. Math. Appl., vol. 19, Springer, New York, 1990, pp. 145 – 165.
[27] S. Sundaram, On the combinatorics of representations of \( {\text{Sp}}(2n,\mathbb{C})\), Ph.D. thesis, M.I.T., 1986.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.