请输入您要查询的字词:

 

单词 DimensionOfAPoset
释义

dimension of a poset


Let P be a finite poset and be the family of all realizersMathworldPlanetmath of P. The dimensionPlanetmathPlanetmath of P, written dim(P), is the cardinality of a member E with the smallest cardinality. In other words, the dimension n of P is the least number of linear extensions L1,,Ln of P such that P=L1Ln. (E can be chosen to be {L1,,Ln}).

If P is a chain, then dim(P)=1. The converseMathworldPlanetmath is clearly true too. An example of a poset with dimension 2 is an antichainMathworldPlanetmath with at least 2 elements. For if P={a1,,am} is an antichain, then one way to linearly extend P is to simply put aiaj iff ij. Called this extensionPlanetmathPlanetmath L1. Another way to order P is to reverse L1, by aiaj iff ji. Call this L2. Note that L1 and L2 are duals of each other. Let L=L1L2. As both L1 and L2 are linear extensions of P, PL. On the other hand, if (ai,aj)L, then aiaj in both L1 and L2, so that ij and ji, or i=j and whence ai=aj, which implies (ai,aj)=(ai,ai)P. LP and thus dim(P)=2.

Remark. Let P be a finite poset. A theoremMathworldPlanetmath of Dushnik and Miller states that the smallest n such that P can be embedded in n, considered as the n-fold product of posets, or chains of real numbers , is the dimension of P.

References

  • 1 W. T. Trotter, Combinatorics and Partially Ordered SetsMathworldPlanetmath, Johns-Hopkins University Press, Baltimore (1992).
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 10:24:11