(0,1)-矩阵的对称链分解

Symmetric Chain Decomposition of (0,1)-matrices

自１９５１ 年ｄｅ Ｂｒｕｉｊｎ 等人提出了对称链概念后，人们用这个特殊的偏序得到了许多优美的结果．如果一个偏序集可以分解成不相交的对称链之并，则称此偏序集具有对称链分解．目前已证明具有对称链分解结构的偏序还不多．把任意一个（０，１）－矩阵Ａ 中的某些１ 变成０ 得到的矩阵叫做Ａ的导出矩阵．Ｌ（Ａ）表示Ａ及其Ａ的所有导出矩阵所组成的集合，在Ｌ（Ａ）上定义序关系＞ ：Ｐ１＞ Ｐ２，其中Ｐ２ 是Ｐ１ 的导出矩阵．本文构造性地证明了偏序集（Ｌ（Ａ），＞ ）具有对称链分解．

Many beautiful results have been derived by symmetric chain since de Bruijn introduced it in 1951.A poset is called a symmetric chain decomposition if the poset can be expressed as a disjoint union of symmetric chains.A matrix P 2 is called a derived matrix of a (0,1) matrix P 1 if P 2 is obtained by changing some elements 1 into 0 in matrix P 1.L(A) denotes the set of A and its all derived matrices.Define order> as follow: P 1>P 2 if and only P 2 is a derived matrix of P 1.The poset (L(A),>) can be expressed as a disjoint of symmetric chains by constructive method.