（应用数学专业论文）超平面排列中的一些问题.pdf

ab s t r a c t a fi n it e h y p e r p l a n e a r r a n g e m e n t 人i s a fi n i t e s e t o f a f fi n e h y p e r p l a n e s i n s o m e v e c - t o r s p a c e v = k , w h e r e ki s a fi e l d , a n d a l i n e a r h y p e r p l a n e i s a n n 一1 d i m e n s i o n a l s u b s p a c e . t h i s p 即o r m a i n l y c o n c e rn s th e b a s i c d e fi n i t i o n o f h y p e r p l a n c a r r a n g e m e n t s ; t h e p r i n c i p l e o f fi n i t e fi e l d s , a n d t h e m e t h o d b a s e d o n fi n i t e fi e l d s f o r c o m p u t i n g t h e c h a r a c t e r i s ti c p o l y n o m i a l o f a n a r r a n g e m e n ts d e f in e d o n q a n d t h e n u m b e r o f r e g i o n s , s o m e c o m b i n a t o r i a l i n t e r p r e t a t i o n s o f r e g i o n s f o r l i n i a l a r r a n g e m e n t a n d s h i a r r a n g e - m e n t , e s p e c ia l l y c o m p u t i n g th e c h a r a c t e r i s t i c p o l y n o m i a l s o f l i n i a l a n d s h i h y p e r p l a n e a r r a n g e m e n t s , t h e c h a r a c t e r i s ti c p o l y n o m i a l s o f a c l a s s o f h y p e r p l a n e a r r a n g e m e n t s ; t h e d i s ta n c e e n u m e r a t o r p o l y n o m i a l o f s h i a r r a n g e m e n t , t h e d i s t a n c e e n u m e r a to r p o l y n o- m i a l s o f s u p e r s o l v a b l e a r r a n g e m e n t s . t h e c o r e c o n t e n t i s t o c o m p u t e th e c h a r a c t e r i s t i c p o l y n o m i a l s o f h y p e r p l a n e a r r a n g e m e n t s b y t h e m e th o d o f fi n i t e fi e l d s , a n d t o t a l k a b o u t t h e c o m b i n a t o r i a l i n te r p r e t a t i o n s o f t h e r e g i o n s o f l i n i a l a n d s h i h y p e r p l a n e a r r a n g e - 立t e n 招. k e y w o r d s : h y p e r p l a n e a r r a n g e m e n t , p a r k i n g f u n c ti o n , c h a r a c t e r i s t i c p o l y n o m i a l , g e - o m e t r i c l a t t i c e , d i s t a n c e e n u m e r a t o r p o l y n o m i a l 南 开 大 学 学 tt 论 文 电 - 3 4 版 授 丰 s c i x用 协 议 ( 请将此协议书装订于论文首页) 论文 南开大学工作和学习期间创作完成的作品，并己 通过论文答辩。 系本人在 本人系本作品的唯一作者 ( 第一作者)，即著作权人。现本人同意将本作品收 录于 “ 南开大学博硕士学位论文全文数据库”。 本人承诺:己提交的学位论文电子 版与印刷版论文的内容一致，如因不同而引起学术声誉上的损失由本人自负。 本人完全了解 南同意 南开大学图书馆在下述范围内免费使用本人作品的电子版 : 本作品呈交当年，在校园网上提供论文目 录检索、文摘浏览以及论文全文部分 浏览服务 ( 论文前1 6 页) 。公开级学位论文全文电 子版于提交1 年后， 在校园网上允 许读者浏览并下载全文. 注:本协议书对于 “ 非公开学位论文”在保密期限过后同样适用。 院系所名称: 作者签名 : 学号: 日期;年月日 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、 保存、 一 使用学位论文的规定， 同意如下各项内容:按照学校要求提交学位论文的印刷本和电子版 本; 学校有权保存学位论文的印 刷本和电 子版， 并采用影印、 缩印、 扫描、数字化或其它手段保存论文;学校有权提供目 录检索以及提 供本学位论文全文或者部分的阅览服务;学校有权按有关规定向国 家有关部门 或者机构送交论文的复印件和电子版;在不以 赢利为目 的的前提下，学校可以适当复制论文的部分或全部内 容用于学术活 动。 学位论文作者签名: 年月日 经指导教师同意， 本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名:学位论文作者签名: 解密时间:年月日 各密级的最长保密年限 及书写格式规定如下: 内 部6 年 ( 最长导 年， 可少于5 年) 默10 f (r - i() i i it- 1 10 -? 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文， 是本人在导师指导下， 进行 研究工作 所取得的成果。 除文中己经注明引用的内 容外， 本学位论文 的研究成果不包含任何他人创作的、 己 公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出 贡献的其他个人和集 体， 均己 在文中以明确方式标明。 本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名: 年月日 第一章 引言 第一章引言 1 .1 超平面排列的 基 本介绍 在引入超平面的概念之前， 我们首先来看下面一个问题: 给定一块蛋糕， 然 后用一把刀对其切割n 次， 问怎样切割蛋糕才能使切割后得到的块数最多? 我们 可以这样转化: 把每一刀看作一个超平面， 那么所切的。刀就构成一个超平面排 列， 怎样的一个超平面排列才能满足要求呢? 问题的答案是这些超平面排列必须 处于所谓的“ 一般位置” 才能满足要求， 即任何两个超平面必须有一条交线、 任 何三个超平面必须有一个交点并且这些交点是互不相同的。 一个超平面是指n 维线性空间中的一个。 一1 维的线性子空间， 比较重要的 进 展由t . z a s l a v s k y 在 2 2 中 给出， 作者主要 运用了 删除限 制的 方 法来推导有 关 超平面排列的特征多项式以及区域个数等有关计数问题的递推关系式， 一个类似 的结 果由m. l a s . v e r g n a s 独立地发 现. 此外， t . z a s l a v s k y 引进了 超平面 排列中 一 个 很 重 要 的 概 念: 超 平 面 排 列 的 相 交 偏 序 集l ( a ) ， 同 时 使 用 莫比 乌 斯 函 数 来 定 义侧 川的 特 征 多 项 式。 更 多 的 进 展 由 p o r lik 以 及l . s o lo m o n 在1 9 8 0 年 的 文 章 9 中 使用组 合数 学的方 法得到。 当超平 面排列 在复空 间 上定义的时 候， 要很 好地研究它们相关的性质需要用到大量的代数、 拓扑等方面的知识。 一个很好的 探索 超平面 排列的 现 代理论可 参见文献 6 ， 更多 其它内 容的 研究请见参 考文献 1 0 。 本文主 要从 组合 数学的角 度来 研究超平 面 排列的 有关问 题。 在下面一些章节中， 我们将会看到有关超平面排列的区域可以 通过它的特征 多项式求出. 那么如何求特征多项式呢? 虽然超平面排列问 题比较复杂并且一般 很难求出它们的 特征多项式， 但是有时候可以计算出特征多项式的生成函数， 甚 至是 它的t u tt e 多 项式， 文章 1 对这个问 题做了 很详 细的 研究 并给出了 求超平 面排列的t u tt e 多项式的多种方法. 求特征多项式的另一个比较有效的方法是有 限 域 方法， 它的 基 本思想 来源于c r a p 。 以 及r o t a 。 虽然 一般 超平面的 特征多 项式 很难求出， 但用有限域方法可以 求出一类超平面排列的特征多项式， 并且它们的 特征 多项式 一 般都很 简单。 在c h r i s t o s a . a t h a n a s i a d i : 的 文章 2 中 做了 非常 具体 的计算与研究。 值得一提的是对于一类特殊的 超平面排列， 它们的特征多项式可 第一章 引言 以写成因子乘积的形式。 l i n i a l 超平面排列区域与光滑偏序集以及满足某些性质的有向竞赛图之间有 一个双射， 这个组合 解释由a l e x a n d e r p o s t n i k o v以 及r i c h a r d p s t a n l e y 在文献 1 1 中 给出 。 l i n i a l 超 平面排 列区 域的数目 恰好 就是顶 点集为 n + 1 的 交错 树的 个数， 并且两位作者在上述文章中也给出了该计数. s h i 超平面排列区域的组合 性 质的 研究 主要参 见r i c h a r d p s t a n l e y 的 文 章 1 6 ， 并 且在该篇文 章中， 作 者证 明了s h i 超平面排列的区域与停车函数是对应的， 同时给出了一个很好的双射。 另外作者通过对 s h i 超平面排列区域的 刻画给出了它的距离计数多项式， 并且证 明了 这 个多 项 式与以0 为 根的 顶点 集为 二 十 1 的树的 逆 序多 项式有 密切 联系。 此 外， c h r i s t o s a . a t h a n a s i a d i s 给出了s h i 超 平 面排列的 区 域和 满足某 种条 件的 偏序 集之间的 一 一对 应， 详 细内 容见 参考文 献 3 . 本文 的 大体框 架 如下: 在 第二 章中， 我 们引 入超平 面排列 相关的 基本 概念 及基本 定理、 给出 拟阵以 及几何格与超平面排列之间的关系，引入超可解超平面排列的定义，最后给出 wh i t n e y 定理的 证明。 定理 1 . 1 . 1 ( w h i t n e y 定理) . 滋是。 维向 童空间 的 超平面 排列， 那么风的 特 征 多项式为 x a (t ) =又 ( - 1 ) # g 。 一、 (。 . 日 ca 定理 1 . 1 .2 . 首先 令( 通 ， 才， 测) 是一 个实 超平面 排列 的三 元数组， 那么 x a ( t ) =x a ( t ) 一 x a ( t ) , r ( a ) 二r ( 才) +r ( a ) , “ ， 一 ;一 ， + “ r a n k ( a ) = r a n k ( a) , r a n k ( a ) = r a n k ( 才) +1 . 对于超可解超平面排列有下面的定理: 定理 1 . 1 3 . l 是秩为n的 超可解的 几 何格， 并且 有一个 模极大 链6 =x 0 二 : 二 : ( 。 = = * h , n - 二 n 凡=0 . 例如， n=2 时， 一些直线的集合处在一 般位笠， 其中没有两条直线是平行 的， 没有三条直线 相交于一点. 定义2 . 1 爪 一个超平面 排列是中 心的， 如果这个超平面 排列中所有超平面的 交集不 是空 集， 即n h尹0 . 如果x= n h ， 那么r a n k ( 川二c o d i m ( x ) . he a hc a 下面介绍一个把超平面排列中心化的算子叫做锥运算: 设a是k n 里面的仿射超平面排列， 并且由下面的等式来决定: l , ( 劝二a , , , l m ( 幻=am 那么 通过引入一个新的坐标p 来定义一个中心的 超平面排列c a如下: 即 l i ( x ) =a i 1/ , 这样我们就可以 推出: 叹 c a ) = 一 ， l m ( 习=%， ， ， =0 二 2 r ( 川， 例2 . 1 . 2 。 在一条直线上的 超平面 排列， -. 一. . . . . 心 . 一一口一.种种种种种种今 -. 1 2 3 那么c ,a的图形为 第二章 基本概念 互 2 .2 超平面排列的 相交 偏序集 定义2 . 2 . 1 . 给定 一个集合尸以及一个 二元关系， 对于所有的x , y ， 二 e尸 ， 满足下面的公理， 称集合 尸是一个偏序集. ( 1 ) 自 反性: x x . ( 2 ) 对称 性: 如果: _ x . ( 3 ) 传 递 性: 如果: ， ， ， : ， 那么二 z . 如 果 在 偏 序 集里 面二 y ， 那么闭 区间x , y = z e 尸: x z y 卜注意: 0 不是闭区间。 定 义 2 .2 .2 . 风是v里面 的 一 个 超 平 面 排列 ， 侧 川里 面 用 反包 含 关 系 定 又 偏 序集， 即 : 对于 任意 的x , y e l ( a ) ， 如果二 ?y ， 那么二 _v ， 因 此可记v=o . 如 果二 ， 并 且 没 有: 任 尸 ， 满 足x : y ， 我 们 称， 及盖二 ， 记 做二 ， 一个 有限 偏序集p的h a s s e 图 可以 通过以 下的 方 法达到， 对于 任意的x , y e 尸: ( 1 ) 首先尸中的元素 作为点。 ( 2 ) 如果x c y ， 那么二 与， 之间 连接一 条边. ( 3 ) 如果x ， ， 那么x 要在， 的 下面。 在一个偏序集里 面， 长度为k 的 链是一个集合二 。 二 : x k 。 如果 x o x i x 2 . . . x k r 那么这条链称为 饱 和的。 如果p 里面的 每一条极 大链的 长 度为都相等且为。 ， 那么我们称偏序集p是分层的， 井且秩为。 。 在这种情况下， 偏序集有一个阶函数: 第二章 基本概念 定义2 . 2 3 . r k : p*n , 1 . r k ( x ) 2 . r k ( y ) 0 ， 其中x 是尸的 最小元。 r k ( x ) 十1 ， 如果: y . 如 果二 ， y e 尸 ， 并 且二 ， ， 那么r k ( 二 ， y ) = r k ( y ) 一 r k ( x ) ， 也 就 是闭 区 间 x , y ) 的长 度。 同样关于超平面排列的偏序集可以得到下面的性质: a是空间v里面的超 平 面 排 列， l ( a ) 是 分 层的 ， 并 且l ( a ) 的 阶 等 于 超平 面 排列a的 秩。 l ( a ) 的 阶 函数是: r k ( x ) =c o d i m ( x ) =。 一d i m ( x ) . 其 中d i m ( x ) 是x 作 为v的 仿 射 子 空间 的 维 数。 下面引出超平面排列的特征多项式的定义: 定 义 2 .2 a 一 个 偏 序集 是局 部 有限 的当 且 仅当 每一 个区 间(x , y ) 是 有 限 的 . 令i n t ( p ) 表示 偏 序集尸里面 所 有闭 区 间 的集 合 : 给定 一 个函 数f : i n t ( p ) z ， 记f ( x , y ) 表示f ( (x , y d . 首 先 定义 莫 出 乌 斯函 数， 设p 是一个局部有限的 偏 序集 ， 定义函 数a = 4 p , i - t ( 玛、 z , 我们用下面的 条件表示 : 1 . 风 二 ， 司=1 , 对于 任意 的x e 只 2 . 风 二 ， 功=一艺 风 x , 习 ， 对于 所 有的x y z z 1 , j ( p ) 表示 所 有的 下 面 的 函 数的 集 合， 对 于 任意两 个函 数f , 9 e j ( p ) ， 定义f 与9 的 乘积: f 9 (x , y ) =e f (x , z ) 9 (z , y ) . s - v 这样， 我们令 b ( 二 ， p/ ) ， ; : a= y , z y - 可以 得出 时于 任意的f e j ( p ) , f b ( 二 ， y ) = f ( t , 1/ ) , b f ( x , y ) = f ( 二 ， 办 因 此可以 看出b 是 单 位 元. 同 时 令c e j ( p ) ， 则 对 于 所 有的二 _ x 证 明 . 所 有的p -1k 的 集 合ii c p 形 成 一 个向 量 空 间 ， 定 义 在j ( p ) 中 作 用 在 向量空间上的线性变换如下: ( ， ) = ec ( 二 ， 。 ) ， ( ; ) ， 其中f e 1k p ， 并且f e j ( p ) . 由莫比乌斯反演公式可以得到下面的结论: c f二9 *f=w 9 2 .3 超平面排列的特征多项式 定 义2 .3 . 1 . 设l ( 川 是 超平面 排列a 列的特征多项式为 x .a ( t ) 一艺 的相交偏序集， 那么我们定义超平面排 m ( 二 ) t d im ( 二 ) . e l ( a ) 第二章 基本概念 例 2 . 3 . 1 . q a = x y ( x + y ) ( x 一 y ) 的 相交 偏 序集 如 下图 : 因 此根 据上面 的 定义， 它的 特 征多项式是x a ( t ) =沪一 4 t + 3 . 很容易可以看出 x a ( t ) = t 0 一 ( # a ) t - + . 下面介绍超平面排列相交偏序集的一些性质: 首先给出一些简单的定义， 对于超平面排列a的一些子排列召 ， 且召c儿 那么c i 仍然是v里 面的 超平面排 列， 同 时 对于x e l ( a ) ， 定义人 9a 凡 = 万任 滩: 二 c h , 同时 对于任意的二 l ( a ) ， 可以 定 义一个在仿射子空间二 内的 超 平面排列a s a s = x f 1 h340 : h a一 凡 . 注 意 到x e l ( a ) ， 那 么l ( a s ) = v z := y l ( a ) : ， 全 好 为了得到超平面排列特征多项式的递推关系式， 我们可以定义以下三元数组， 首先选择h o e a ， 令a =a一 h o , a =a h o ( 限 制到h o 上面 ) ， 这里的h o 可 以 称为 特殊超 平面， 因 此我们定 义超平面排列的 三 元数 组为( a , a , a ) , 就可以 得到下面的定理: 引理 2 .3 . 1 . 首 先 令( a , a , a ) 是一个关于超平 面 排列h o 的 三元数组， 那么 r ( a ) =二 ( a ) +r ( a ) “( ， 一 ;一a ， 十 “ ， r a n k ( a ) =r a n k ( , 4 ) , r a n k ( 川 =r a n k ( x) +1 . 第二章 基本概念 证明 . 首 先r ( a ) 等 于叹 a ) 再 加上才的 区 域 里 面 被h o 分成两 部 分的 那 部 分区 域， 如 果 对于 任意的 区 域r e r 洲) ， 那 么r n h o e r ( a ) 。 同 样， 如果 r e r ( a ) ， 因 为 对 于h e r ( a) , h必 定 与r 相 交， 因 此r 被h o 分成 两部 分， 我们也可以 给出 在a 里面被h o 切成的 区域与a 的区 域之间的双射， 这样 就可以得到上面的递推关系式。口 定理 2 3 . 2 ( d e l e t io n - r e s t ri c t i o n 定理) . 首 先 令( a , a, a ) 是一个实 超平面 排 列的 三 元 教 组 ， 那么x a w = x a ( t ) 一 x a ( t ) - 要证明上面的定理需要引入下面几个引理， 同时我们必须引入格的概念。 定义2 3 . 2 . 设尸是一个偏序集， 对于x , y e 尸 ， 定义: 尸 ， 且: 为x 与y 的 上界， 那么z 七x 并且z 全势 二 与， 的 最小 上 界为二 v y ， 即x v y 是一个上 界， 且对于工 ， ， 所 有的 上界 z , x v y = x , yel , 口 命 题 2 3 .4 . a是 一个 超平面 排列 ， 那么l ( a ) 是 一个 交 半 偏 序格， 且 是l ( a ) 的 每 一个间 隔x , y 1 是一 个 格 . 并 且l ( a ) 是 一个 格当 且 仅当a是一 个中 心的 超 平面排列。 证 明 得到l ( a ) 如果 门h二0 ， 那么 增加0 到l ( a ) 作 为唯 一的 最 大元， 这 样 我们 he a 的 一个增 广相交 偏序集l ( 川。 在l ( a ) 里面， 很明 显x v ?/ =x 门 y , 第二章 基本概念 并 且l ( a ) 是 一 个 联 合 半 偏 序 格. 因 为o e l ( a ) , 所 以l ( a ) 是 一 个 格 ， 又因 为 l ( a ) =l ( a ) 或 者l (a ) =l ( a ) 一 1 ， 我 们 就 得 出l ( a ) 总 是 一 个 交 半 偏 序 格， 并 且 当a是中 心超 平 面排 列时， l ( a ) 是 一 个 格。 如 果a不是中 心的 ， 得出 v 二 “ (a ) 2 不 存 在 ， 因 此l ( a ) 不 是 一 个 格 。口 定 理2 .3 .5 ( t h e c r o s s - c u t 定理) . 设l 是一 个 有限 格， x是l 的 一个 于集， 同 时x要 满 足0 偌 x ， 并 且 如 果y e l , y 拼 0 ， 那 么 就 存 在x e x ， 满 足: y ， 记 从 是x的k元子集的 数目 ， 所有子集的 并 是1 ， 那么 a l ( 6 , 1 ) = n o 一 n , 十 n 2 一 对于t h e c r o s s - c u t 定理可以用代数的方法证明， 为了节省篇幅， 在这里省 略， 详细的 证明 过程见 1 7 0 定 理2 .3 .6 ( w h i t n e y 定理 ) . 涯是。 维向 量空 间的 超平面 排列， 那么滋的 特征 多项式为 、 ， ( ) =e ( _ 1 ) # b t n - r a n k (b ) . 9 c ab r * . n 证明这个定理需要用到前面的t h e c r o s s - c u t 定理， 为了更好的理解这个定 理， 来看下面的一个例子: 例2 . 3 . 2 . 下面的图形: 首先 要找出通的所 有中 心的 子集 ， 并 且计算# b以 及r a n k s ， 请看 1 . b=0 ， 券 b=0 , r a n k b=0 . 2 . b=a , 赤 b=1 , r a n k s=1 . 3 . b=6 , # b=1 , r a n k s=1 第二章 基本概念 4 . 8=c , 券 b=1 , r a n k s=1 . 5 . b=a 6 , # b=2 , r a n k s二2 6 . b二6 c , 半 b 7 . b=a c , 券 b = 2 , r a n k b = 2 = 2 , r a n k s = 2 . 我们可以得到 x a ( t ) = ( - 1 ) o t z + 3 ( - 1 ) 1 t (z - 1 ) + ( 一 1 ) 2 t (2 - 2 ) = t 2 一 3 t + 3 . 下面 我们 来证明 上面的wh i t n e y 定 理: 证明 . 对 于 任意的: l ( a ) , 那么儿 = he a: h z ， 即 : c h . 通过前面的t h e c r o s s - c u t 定理， 我们可以 得到 ; ( ) =又 ( - 1 ) # b 日caa . z ( a j 牙 es 因 为: =n h , r a n k ( b ) 二 n 一 d i m ( z ) ， 两 边同 时 乘以t n - 可 得 h eb p ( z ) t n - r a n k (b ) =又 ( - 1 ) # b t n - r n n k (b ). bcaa = n x hem 则 x a ( t )= 艺 a (z ) tn - r a n k (b ) - e l ( a ) 艺( 一 ， ) # b t n - ra n k (s ) 石ca 口 利 用上 面的w h i t n e y 定 理， 就 可以 证明 超 平面排列 特征多 项 式的 递推关 系 式， 即前面的d e l e ti o n - r e s t r i c ti o n 定理。 定理 2 3 .7 田e l e ti o n - r e s t r i c ti o n 定 理 ) . 首 先 令( 滩 ， 才， 才) 走 一 个实 超 平 面 排 列的 三元数组， 那么x a ( t ) = x a ( t ) 一 x .a 0 ( 幻 . 第二章 基本概念 证明 .设a是一个超平面排列， 超平面h o a ， 同时 定义一个三元数组 ( a , a , x) ， 然 后 按照h o e 8 以 及h o 磷 b 的 分类， 把 上 面的w h i tn e y 定 理 分 为 两部分， e ( - 1 )# b tn - r an k (b ) = x a i(t ), x p b c a 石是中心的 令b l =( b 一 h o ) h o ， 一 个中 心 超平 面h o - ii c n - 1 ， 并 且 一 个 子 超 平 面 排 列a h = a b ， 因 为# 1 3 1 二# b一 1 ， 同 时r a n k ( b l ) =r k ( 功一1 ， 我们 得 到 艺 ( - 1 ) # b t n - r a n k (b ) - e a u o b 1 互 a 吕 1 是 中 心 的 _ x a( t ) ( - 1 ) # b 1 + 1 t n - 1 j r a n k (b 1 ) 月 。 四 c a 万月中心的 口 下面通过特征多项式我们来求出超平面排列区域的个数以及有界区域的个 数， 具体的 证明过程可以 见参考文献 1 7 . 定理2 .3 . 8 . 设滋是一个。维超平面排列， 则 r ( 川 二( 一 1 ) n x a ( - 1 ) , b ( a ) 证明 首 先a=0 时， r ( a ) =( 一 1 ) r a n k (a ) x a ( 1 ) =1 、 有x a ( t ) =t o ， 并 且通过前面的 证明 可以 看到叹 为与卜1 ) n x a ( - 1 ) 满 足 相同 的 循 环. 同 样 可以 证明b (a ) =( _ 1 ) r a n k (a ) x a ( 1 ) 推 论 2 3 . 9 . a是一个实 超平面 排列 ， 那么r ( a ) 与试 川仅取决于l ( a ) . 2 .4 拟阵以及几何格与超平面排列的关系 这 里只 是 大体介绍 拟阵以 及与 超 平 面排列的关系， 拟阵的 概念最早由w i tn e y 在 1 9 3 5 年第一次引进， 它是向量空间一个向量集合的抽象。 这里从独立集的方 面引入拟阵， 首先来看一下拟阵的定义: 定 义 2 .4 . 1 . 对于 任何 集 合s ， 我 们 记2 s = t: tcs ， 有限 拟 阵 是m= (s,3)， 其中s 是有限 集 ， 3 是s 中 子 集的 集 合， 满 足下 面 的 条 件 : 。1 4 。 第二章 基本概念 1 . 是非空的 抽象的 单纯形， 即j 兴0 ， 并且 如果j e 3 以 及i cj ， 那么i e 尔 2 . 对于所 有的tcs , a n了的最大元有相同的 基。 打个比方， 向量空间的一个有限集合 s ， 那么这里所说的独立就是线性无关. 例2 .4 . 1 . 在仿射空间1 8 2内的五个点， 如下图: ( d ) 因 为 1 , 2 , 3 , 1 3 , 4 , 5 都 在直线 上， 这样它 们是 相关的 。 因 此m的 独立 集 至 多包 舍含 有两 个元 素的 集 合 ， 或者包 含除 了 集 合 1 , 2 , 3 , 3 , 4 , 5 之外 的所 有的 含有三个元 素的集合. ( b ) 记z= ， 是由13= 生成的 单纯形.同 时j = , 3 不 是一个独立集 ，因 为j n 2 1 ,2 .4 ) ， 且2 1 2 4 ) = 1 1 , 2 , 3 , 1 2 , 1 4 , 2 4 , 1 2 4 , 0 ， 所以j n 2 1 .2 ,4 的 极大 元是1 2 和4 ， 显然 它们不 具有 相同的个数. 下面我们来 看与拟阵有关的几个比较重要的概念 定义 2 .4 .2 . ( 1 ) 圈 指的 是最小的非独立集， 也就 是说， c 本来 是不独立的 ， 但 是去掉其中 任何一个点之后就独立了 ; ( 2 ) 知果m=( s , -3 ) 是一 个拟 阵 ， 并且tcs ， 那么 我们来定 义t 的秩， 即r k (t ) r k ( 刀=二 # i : i e 3 ， 并且i ct , 特别 的 ， r k ( 0 ) = 0 ， 同时 定 义 拟阵本身的 秋为 r k ( m) = r k ( s ) ; ( 3 ) 一个k平台 是指秋为k的 极大子集， 同 时可以 证明 任何k平台的交仍然是 平台， 因 此可以 给出 平台闭包 的概念; ( 匀设t 是s 的 一个 子集 ， t 的 闭包 就是包 含t的 最小 的 平台 ， 即 ， =门f . fd t 第二章 基本概念 ( 5 ) 设m 是一个 拟阵 ， 定义l ( m) 是关于m 平台的 偏序集， 偏序关系 是平台 之 间 的 包 含 关 系 ， 因 为 平台 的 交 还 是 平 台 ， 因 此l ( m ) 是 交 半 格 ， 又 因 为l ( m ) 有一 个极大 元， 因 此可以 推出l ( m) 是一个格， 同时l ( m) 是关 于秋的 分层 格， 即l ( m ) 的 每 一 个 极大 链 的 长 度 都 相 等 ; 这样， 知果x n = * h l n n 凡 =0 . 对于一 般位置的 超平 面排列， 我们可以 得 到 下面的定理， 并 且求出 它的 特 征 多项式。 定理 2 . 5 . 1 . 设摊是一般位 里的 超平面 排列 ， 对于 任意z i 二 a , 同时# b n , 那么二 ， = 门 h是l ( a ) 的一 个元 素， 这 样可以 得到l ( a ) 与 一 个布尔 代数同 h e日 构， 即 l ( a ) = s c脚 : # s 6 ， 我 们 需 要 证 明 习- 1)rk (xx y ， 一 0 ， 那 么 r k (x ) 一 的 个 数(k) , (i k ) ， 则通过二项式展开有， ki=0 (:)一，一 0, 因此有 p ( x ) =( 一 1 ) 气 所以有 x a ( t ) =e(一 ) # s t ” 一 # s = t o 一 。 t n - 1 s s m l# s _ _ 、 _ / 价 + 二 十 卜 1 ) . i i . 几/ 定义2 5 . 2 . 图 超平面 排列州 月 在k n 里面的超平面排列 ， 二 一x j = 0 , i i e e ( g ) . 同 时我们定义图染色 多项式的定义 : 设g 是定 义 在n , 个 顶 点 上 的 图 ， 染色 多 项 式 是 一 个 映 射 : 二in 一 尸 ， 、 为 正常 染色 ， 任 何 两 点 的 数 值 都 不 相 同 ， 当红e g时 ， 有减 动 尹 减 力 . 如果q e 尸 1 那么x g (q ) 指的 是正 常 染 色。- - q 的 个 数 ， 那么 函 数x g 叫 做g 的 染色 多 项式。 定 理 2 5 .2 . 我 们 可以 证明 对于 任 何图 形g ， 有x a (t ) = x g (t ) ， 也 就 是 说图 超平面 排列的 特征多项式与图的染色 多项式是对应的. 定义 2 . 5 . 3 . 图的定向指的 是给图 的 每一条边都安排一个 方向， 或 者i - j ， 或 者j - + i ， 其中ii e g ， 一 个 有 方 向的 图 指 的 是 点g 的 一 个 序列i 1 ， 二 ， , ik ， 其中 i o i 1 _ , . . ， 一i k - i p 在。 . 如果 一个图不包 含任何一个 有向圈， 则我 们说它 是无圈的。 命 题2 . 5 . 3 . 设 。 是g的一个定向， 那么 对于r e r ( .a g ) , o = o r 当 且 仅当。 是 无圈的。 第二章 基本概念 证 明 . o r 有 一 个 圈 : *i 2 * 二 *i k *i l ，