和矩阵相关联的偏序集的跳跃数

摘要

A=（aij)表示→m×n阶矩阵。可把偏序集PA和A自然联系起来。用X={x1,x2，……xn}和Y={y1,y2,……yn}表示不交的m和n元集，定义xi＜yi当且仅当aij≠0。PA的Hasse图就是通常A的二部图，其中y'sx's的上面。称PA为二部偏序集。偏序集PA的跳跃[阶梯]数是最小[最大]跳跃[阶梯]的数目。（PA的线性扩张中的一个跳跃是PA中一对不可比较的元素，否则称为阶梯）。文章主要研究了二部偏序集的跳跃数和其Hasse图结构的关系，并给出一个确定PA阶梯数的递归算法。