偏序集区间广义拟阵及其性质
2018-03-07李尧龙
李 尧 龙
(渭南师范学院 东盟博仁财经学院，陕西 渭南 714099)
0 引言
拟阵理论最早由Whitney于1935年提出，他主要研究了定义在一个有限集合的子集合上的抽象相关关系，并且系统地给出了拟阵的公理体系。 此后, Birkhoff、Maclane、Dilwurth等人研究了拟阵的几何问题及拟阵与格论的关系。直到 20世纪60年代,Tutte把拟阵与图论充分结合起来并做了大量工作，拟阵理论才取得了长足的发展。[1]拟阵理论是近几十年发展起来的离散数学的一个重要分支，拟阵作为同时推广了图论与向量空间的一门理论学科，已经被广泛应用于组合优化、整数规划、网络流、信息安全等多个领域。
由于实际问题研究的需要，拟阵的独立集系统弱化成为研究的方向之一。1991年,B. Korte and L. Lovasz[2]将拟阵的独立集系统弱化，得到了广义拟阵理论。 广义拟阵理论在格论、 组合优化和线性规划理论等方面有很好的应用。 与其他数学分支的结合产生了多种广义拟阵，如凸几何、反拟阵等。[3-5]后来有许多学者研究了广义拟阵理论。 广义拟阵的研究有十分丰富的内容,B. Korte and L. Lovasz在他们的专著Greedoids中指出:广义拟阵不仅是拟阵与反拟阵的推广，而且覆盖了大量其他的数学结构,广义拟阵有十分丰富的内容。
偏序集拟阵是用一个偏序集代替拟阵的底集，底集的子集被偏序集的滤子(或对偶的，序理想)替换而发展起来的一套理论。 这一理论被意大利学者Barnabei等人提出并进行系统研究。[6-9]他们还从偏序集拟阵和组合概型两个方面详细研究了偏序集拟阵的公理体系。 偏序集拟阵在投射几何、代数学等方面有很好的应用。
在实际问题的研究中,与偏序集拟阵类似,如果将广义拟阵的底集由偏序集替换，底集的子集被偏序集的滤子(或对偶的，序理想)替换, 我们将得到偏序集广义拟阵。 偏序集广义拟阵在格论、组合优化理论等方面有很好的应用背景。[10]区间广义拟阵是很重要的一类广义拟阵，区间广义拟阵有十分丰富的性质，并且与拟阵、反拟阵有密切的关系。 本文研究一类特殊的偏序集广义拟阵——偏序集区间广义拟阵的性质;研究了偏序集区间广义拟阵与偏序集拟阵的关系，并且给出偏序集区间广义拟阵的等价刻画; 研究了偏序集区间广义拟阵的子广义拟阵的性质以及偏序集区间广义拟阵的直立的区间性等，这些研究丰富了偏序集广义拟阵的内容。
1 预备知识
为完整起见,以下给出本文用到的一些主要概念与性质。
设(P,≤)为有限偏序集(以下简记为P)。 对P的任意子集A,定义Max(A)={x∈A|x是A的极大元}，Min(A)={x∈A|x是A的极小元}, 对P的任意元x和y,x≤y,区间[x,y]定义为[x,y]={z∈P|x≤z≤y}。如果[x,y]的基数是2, 则称x被y覆盖, 记为xy。P的滤子A是P的子集使得对于任意x,y∈P, 如果x≥y且y∈A, 那么x∈A,P的滤子集记为F(P)。
如果A∈F(P), 且x是A的极小元,y是PA的极大元, 则Ax∈F(P),A∪y∈F(P)。
定义1[3]设P为有限偏序集,ζ为P的滤子集且满足以下条件:
(I) ∅∈ζ;
(II)对任意的X∈ζ且Y⊆ζ, 则Y∈ζ;
(III)对任意X,Y∈ζ且|Y|<|X|, 存在x∈Max(X-Y)使得Y∪x∈ζ,
则称(P,ζ)为P上的偏序集拟阵,ζ中的元素称为独立集，ζ的极大元称为(P,ζ)的基。
如果把拟阵独立集公理弱化,有以下广义拟阵的定义。
定义2[2]设E为有限集,ζ为E的子集族且满足以下条件:
(I) ∅∈ζ;
(II)对任意X,Y∈ζ且|Y|<|X|,存在x∈X-Y使得Y∪x∈ζ,
则称(E,ζ)为E上的广义拟阵,ζ中的元素称为可行集，ζ的极大元称为(E,ζ)的基。
本文用到的其他概念与性质,请参见文献[2-3,10-11]。
2 偏序集区间广义拟阵的等价刻画
在文献[10]中，由广义拟阵的定义,我们定义偏序集广义拟阵如下。
定义3[10]设P为有限偏序集,ζ为P的滤子集且满足以下条件:
(I) ∅∈ζ;
(II)对任意X,Y∈ζ且|Y|<|X|, 存在x∈Max(X-Y) 使得Y∪x∈ζ,
则称(P,ζ)为P上的偏序集广义拟阵,ζ中的元素称为可行集，ζ中的极大元称为(P,ζ)的基，(P,ζ)的所有基的集合记为β。
如果P为平凡偏序集，则以上定义就是一般的广义拟阵(见定义2)。定理1显然成立。
定理1[11]设(P,ζ)为偏序集广义拟阵，则定义3中(II)成立,当且仅当∀A∈ζ∩F(P),A的所有基有相同的基数(A的基为A中可行集的极大元)。
定义偏序集广义拟阵(P,ζ)的秩函数为
r(X)=Max{|A||A⊂X,A∈ζ}。
对于偏序集广义拟阵(P,ζ)，可以定义闭包算子σ∶F(P)→F(P)如下：
σ(X)={X|A∪X是P的滤子,r(A∪X)=r(A)}。
定义4 设(P,ζ)为偏序集广义拟阵，A，B,C∈ζ∩F(P),A⊆B⊆C, 如果∀x∈Max(P-C),A∪x,C∪x∈ζ∩F(P)，使得B∪x∈ζ∩F(P), 则称(P,ζ)为偏序集区间广义拟阵。
设(P,ζ)为偏序集广义拟阵，∀A，B∈ζ∩F(P)，A⊆B(B⊆A)，∀x∈Max(P-A∪B),若B∪x∈ζ∩F(P)，则A∪x∈ζ∩F(P)，称(P,ζ)为无下界(无上界)偏序集广义拟阵。
区间广义拟阵是一类很重要的广义拟阵，广义拟阵的区间性很好地揭示了拟阵、反拟阵与广义拟阵之间的关系，并且广义拟阵的区间性深刻揭示了广义拟阵的内在性质，其与平衡广义拟阵、拟阵与反拟阵的交、广义拟阵的分块及广义拟阵的圈都有很密切的关系(见文献[2])。
定理2 一个偏序集区间广义拟阵(P,ζ)为偏序集拟阵当且仅当∀x∈MinP,x∈ζ∩F(P)。
证明 若(P,ζ)为偏序集拟阵，则结论成立。
反过来，我们证明∀x∈MinP,x∈ζ∩F(P)，(P,ζ)为偏序集拟阵。
(1)由于(P,ζ)为偏序集广义拟阵,∅∈ζ∩F(P)。
(2)设B∈ζ∩F(P),A为B的极大子偏序集,且A∉ζ∩F(P)。如果∀x∈MinP,x∈ζ∩F(P)，则Ax∈ζ∩F(P), 由偏序集广义拟阵(P,ζ)的性质知,Ax可以从B(Ax)中扩张，则存在C∈ζ∩F(P)，使得Ax⊆C,x∉MinC且C∪x∈ζ∩F(P)。 由于∅∈ζ∩F(P),∅∈Ax⊆C及(P,ζ)为无下界偏序集广义拟阵,有(Ax)∪x=A∈ζ∩F(P),与假设矛盾。
由偏序集广义拟阵的定义，易证(P,ζ)为偏序集拟阵。
定理3 设(P,ζ)为偏序集广义拟阵，A,B,C∈ζ∩F(P)且A⊆B⊆C，则(P,ζ)为偏序集区间广义拟阵当且仅当σ(B)⊆σ(A)∪σ(C)。
证明 若(P,ζ)为偏序集区间广义拟阵，则∀x∈Max(P-C),A∪x,C∪x∈ζ∩F(P)，使得B∪x∈ζ∩F(P),由x∉σ(A)，x∉σ(C)有x∉σ(B),这样σ(B)⊆σ(A)∪σ(C)。
反过来，设A,B,C∈ζ∩F(P),A⊆B⊆C。若σ(B)⊆σ(A)∪σ(C),∀x∈Max(P-C),A∪x,C∪x∈ζ∩F(P)，以下证明B∪x∈ζ∩F(P)。
若B∪x∉ζ∩F(P),则有x∈σ(B)。又由于σ(B)⊆σ(A)∪σ(C),故x∈σ(A)∪σ(C)。
(1)若x∈σ(A),则A∪x∉ζ∩F(P),与假设矛盾。
(2)若x∈σ(C),则C∪x∉ζ∩F(P),与假设矛盾。
故B∪x∈ζ∩F(P),结论成立。
定理4 设(P,ζ)为偏序集广义拟阵,则(P,ζ)具有区间性质当且仅当若A,B,C∈ζ∩F(P),A⊆B且C⊆σ(A),则C⊆σ(B)。
证明 设(P,ζ)为偏序集广义拟阵,若A,B,C∈ζ∩F(P),A⊆B且C⊆σ(A),则C⊆σ(B)。若A,B,C∈ζ∩F(P),A⊆B⊆C,假设∃x∈Max(P-B)(显然有x∈Max(P-C))使得A∪x∈ζ∩F(P),B∪x∉ζ∩F(P),则由A∪x∈σ(B)有A∪x∈σ(C),即有C∪x∉ζ∩F(P)。这样(P,ζ)为偏序集区间广义拟阵。
反过来,设D∈ζ∩F(P)且D∈Max(C∩σ(B))。以下分2种情况讨论:
(1)若D=C(D,C∈ζ∩F(P)),结论自然成立。
(2)若D≠C(D,C∈ζ∩F(P)),则∃x∈Max(C-D),使得B∪x∈ζ∩F(P)(否则∀x∈Max(C-D),有D∪x∉ζ∩F(P),则有x∈σ(D)⊆σ(B),与假设D⊆Max(C∩σ(B))矛盾)。
显然x∉σ(B),否则与D⊆Max(C∩σ(B))矛盾。由定理1,有x∉σ(D)。由已知C⊆σ(A),故有D⊆σ(A)∩σ(B)⊆σ(B)。由定理3,σ(σ(A)∩σ(B))⊆σ(D)∪σ(B)。又因为A⊆σ(A)∩σ(B)⊆σ(B),有σ(σ(A)∩σ(B))⊆σ(A)。这样σ(A)⊆σ(D)∪σ(B)。由C⊆σ(A)知x∈σ(A),但这与(P,ζ)具有区间性质矛盾。
3 偏序集广义拟阵子广义拟阵的区间性
区间性在广义拟阵的研究中有很重要的作用，对广义拟阵来说，其子广义拟阵的区间性研究是有趣的，本节研究偏序集广义拟阵的偏序集子广义拟阵的区间性质。
定义5 设(P,ζ)为偏序集广义拟阵，k∈N,定义ζk为
ζk={A∈ζ||A|≤k,A∈F(P)}。
容易证明(P,ζk)为偏序集广义拟阵。称(P,ζk)为k-截短偏序集广义拟阵。
命题1 设(P,ζ)为偏序集区间广义拟阵,(P,ζk)为k-截短偏序集广义拟阵，则(P,ζk)具有区间性质。
证明 设(P,ζ)为一偏序集区间广义拟阵,(P,ζk)为其k-截短偏序集广义拟阵。A,B,C∈ζk∩F(P),A⊆B⊆C。如果∀x∈Max(P-C),A∪x,C∪x∈ζk∩F(P)，以下证明B∪x∈ζk∩F(P)。由于(P,ζ)为一偏序集区间广义拟阵,以及A,B,C∈ζ∩F(P),A⊆B⊆C。∀x∈Max(P-C),A∪x,C∪x∈ζ∩F(P)，有B∪x∈ζ∩F(P),由于C∪x∈ζk∩F(P),以及B⊆C,有B∪x⊆C∪x,由(P,ζk)的定义,B∪x∈ζk∩F(P)。所以,则(P,ζk)具有区间性质。
定义6 设(P,ζ)为偏序集广义拟阵，T为P的子滤子,定义ζT为
ζT={A∈ζ|A∈T}。
容易证明(T,ζT)为偏序集广义拟阵。称(T,ζT)为限制偏序集广义拟阵。
与命题1的证明类似,我们有以下结论成立。
命题2 设(P,ζ)为偏序集区间广义拟阵,(T,ζT)为限制偏序集广义拟阵,则(T,ζT)具有区间性质。
定义7 设(P,ζ)为偏序集广义拟阵，B∈ζ∩F(P)，定义ζ/B为
ζ/B={A|A∈P-B,A∪B∈ζ}。
容易证明(P-B,ζ/B)为偏序集广义拟阵。称(P-B,ζ/B)为从(P,ζ)到P-B的收缩偏序集广义拟阵。
与命题1、命题2的证明类似,我们有以下结论成立。
命题3 设(P,ζ)为偏序集区间广义拟阵,(P-B,ζ/B)为从(P,ζ)到P-B的收缩偏序集广义拟阵,则(P,ζ/B)具有区间性质。
定义8 设(P1,ζ1)与(P2,ζ2)为偏序集广义拟阵，如果P1∩P2=∅,则有(P1,ζ1)与(P2,ζ2)的直和(P1∪P2,ζ1⊕ζ2)与序和(P1∪P2,ζ1⊗ζ2)，其中：
ζ1⊕ζ2={μ∨v|μ∈ζ1,v∈ζ2}，
ζ1⊗ζ2=ζ1∪{B∨v|B∈β,v∈ζ2}。
容易证明直和(P1∪P2,ζ1⊕ζ2)与序和(P1∪P2,ζ1⊗ζ2)为偏序集广义拟阵。若(P1,ζ1)与(P2,ζ2)为偏序集区间广义拟阵,则直和(P1∪P2,ζ1⊕ζ2)与序和(P1∪P2,ζ1⊗ζ2)具有区间性质。
以上研究了偏序集区间广义拟阵的子拟阵的区间性质，下面给出一个偏序集区间广义拟阵直立的区间性质。
设β为偏序集广义拟阵(P,ζ)的基集,令φ:β→F(P)P具有以下性质:
(I)∀B∈β,B⊆φ(B);
(II)∀B1，B2∈β,若φ(B1)≠φ(B2),则B1⊄φ(B2)。
定义9 设(P,ζ)为偏序集广义拟阵,令
ζ′=ζ∪{B∪x|B∈β,x∈Max(Pφ(B))},
称(P,ζ′)为(P,ζ)的直立。
定理5 设(P,ζ)为偏序集区间广义拟阵,(P,ζ′)为偏序集广义拟阵(P,ζ)的直立,则(P,ζ′)具有区间性质。
证明 首先证明(P,ζ′)为偏序集广义拟阵。由于ζ′=ζ∪{B∪x|B∈β,x∈Max(Pφ(B))},
(I)由ζ′的定义,显然ζ′≠∅。
(II)∀X∈ζ′，证明∃x∈MinX,使得Xx∈ζ′。以下分2种情况:
(1)若X∈ζ，由于(P,ζ)为偏序集广义拟阵，∃x∈MinX，使得Xx∈ζ;
(2)若X∈{B∪x|B∈β,x∈Max(Pφ(B))},显然∃B∈β,使得X=B∪x。所以取x∈Max(Pφ(B)),使得Xx=B∈ζ。
(III)设X,Y∈ζ′,且|Y|<|X|。
(1)若|X|≤|B|,B∈β,则X,Y∈ζ，由于(P,ζ)为偏序集广义拟阵,结论成立。
(2)若|X|=|B|+1,B∈β，则∃x∈Max(Pφ(B))，使得X=B∪x。以下分3种情况:
(i)若|Y|<|B|，则∃x∈Min(B)，使得Y∪x∈ζ;
(ii)|Y|=|B|且φ(Y)=φ(B),则Y∈β,由于Y∪x∈{B∪x|B∈β,x∈Max(Pφ(B))},由ζ′的定义,有Y∪x∈ζ′;
(iii)如果|Y|=|B|并且φ(Y)=φ(B)，由ζ′的定义,∃x∈Max(Pφ(B))，使得Y∪x∈{B∪x|B∈β,x∈Max(Pφ(B))},所以Y∪x∈ζ′。
这样(P,ζ′)为偏序集广义拟阵。以下证明(P,ζ′)的区间性。
设A,B,C∈ζ∩F(P),A⊆B⊆C,如果∀x∈Max(P-C),A∪x,C∪x∈ζ∩F(P),以下证明B∪x∈ζ∩F(P)。
若A=B=C,结论显然成立。
若A⊆B⊆C,主要分为3种情况：
(i)A=B⊂C,结论成立;
(ii)A⊂B=C，结论成立;
(iii)若A⊂B⊂C，如果|C|<|D|,D∈β,则A,B,C∈ζ∩F(P),由于(P,ζ)为偏序集区间广义拟阵，结论成立。若|C|=|D|,D∈β,则∀x∈Max(P-C),有A∪x,C∪x∈ζ∩F(P),由于B⊆C,故B∪x∈ζ∩F(P)。
综上,(P,ζ′)为偏序集区间广义拟阵。
4 结语
本文研究了偏序集广义拟阵区间性质,给出了偏序集区间广义拟阵的3个等价刻画,较为深刻地揭示了偏序集区间广义拟阵的性质。随后研究了偏序集区间广义拟阵的子拟阵的区间性,得到了偏序集区间广义拟阵的直立的区间性。这些结果丰富了偏序集广义拟阵研究的内容,为进一步研究偏序集区间广义拟阵的性质奠定了基础。
