偏序集區(qū)間廣義擬陣及其性質

李 堯 龍

(渭南師范學院 東盟博仁財經學院，陜西 渭南 714099)

0 引言

擬陣理論最早由Whitney于1935年提出，他主要研究了定義在一個有限集合的子集合上的抽象相關關系，并且系統(tǒng)地給出了擬陣的公理體系。 此后, Birkhoff、Maclane、Dilwurth等人研究了擬陣的幾何問題及擬陣與格論的關系。直到 20世紀60年代,Tutte把擬陣與圖論充分結合起來并做了大量工作，擬陣理論才取得了長足的發(fā)展。[1]擬陣理論是近幾十年發(fā)展起來的離散數(shù)學的一個重要分支，擬陣作為同時推廣了圖論與向量空間的一門理論學科，已經被廣泛應用于組合優(yōu)化、整數(shù)規(guī)劃、網絡流、信息安全等多個領域。

由于實際問題研究的需要，擬陣的獨立集系統(tǒng)弱化成為研究的方向之一。1991年,B. Korte and L. Lovasz[2]將擬陣的獨立集系統(tǒng)弱化，得到了廣義擬陣理論。 廣義擬陣理論在格論、 組合優(yōu)化和線性規(guī)劃理論等方面有很好的應用。 與其他數(shù)學分支的結合產生了多種廣義擬陣，如凸幾何、反擬陣等。[3-5]后來有許多學者研究了廣義擬陣理論。 廣義擬陣的研究有十分豐富的內容,B. Korte and L. Lovasz在他們的專著Greedoids中指出:廣義擬陣不僅是擬陣與反擬陣的推廣，而且覆蓋了大量其他的數(shù)學結構,廣義擬陣有十分豐富的內容。

偏序集擬陣是用一個偏序集代替擬陣的底集，底集的子集被偏序集的濾子(或對偶的，序理想)替換而發(fā)展起來的一套理論。 這一理論被意大利學者Barnabei等人提出并進行系統(tǒng)研究。[6-9]他們還從偏序集擬陣和組合概型兩個方面詳細研究了偏序集擬陣的公理體系。 偏序集擬陣在投射幾何、代數(shù)學等方面有很好的應用。

在實際問題的研究中,與偏序集擬陣類似,如果將廣義擬陣的底集由偏序集替換，底集的子集被偏序集的濾子(或對偶的，序理想)替換, 我們將得到偏序集廣義擬陣。 偏序集廣義擬陣在格論、組合優(yōu)化理論等方面有很好的應用背景。[10]區(qū)間廣義擬陣是很重要的一類廣義擬陣，區(qū)間廣義擬陣有十分豐富的性質，并且與擬陣、反擬陣有密切的關系。 本文研究一類特殊的偏序集廣義擬陣——偏序集區(qū)間廣義擬陣的性質;研究了偏序集區(qū)間廣義擬陣與偏序集擬陣的關系，并且給出偏序集區(qū)間廣義擬陣的等價刻畫; 研究了偏序集區(qū)間廣義擬陣的子廣義擬陣的性質以及偏序集區(qū)間廣義擬陣的直立的區(qū)間性等，這些研究豐富了偏序集廣義擬陣的內容。

1 預備知識

為完整起見,以下給出本文用到的一些主要概念與性質。

設(P,≤)為有限偏序集(以下簡記為P)。 對P的任意子集A,定義Max(A)={x∈A|x是A的極大元}，Min(A)={x∈A|x是A的極小元}, 對P的任意元x和y,x≤y,區(qū)間[x,y]定義為[x,y]={z∈P|x≤z≤y}。如果[x,y]的基數(shù)是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 偏序集區(qū)間廣義擬陣的等價刻畫

在文獻[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的所有基有相同的基數(shù)(A的基為A中可行集的極大元)。

定義偏序集廣義擬陣(P,ζ)的秩函數(shù)為

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,ζ)為偏序集區(qū)間廣義擬陣。

設(P,ζ)為偏序集廣義擬陣，?A，B∈ζ∩F(P)，A?B(B?A)，?x∈Max(P-A∪B),若B∪x∈ζ∩F(P)，則A∪x∈ζ∩F(P)，稱(P,ζ)為無下界(無上界)偏序集廣義擬陣。

區(qū)間廣義擬陣是一類很重要的廣義擬陣，廣義擬陣的區(qū)間性很好地揭示了擬陣、反擬陣與廣義擬陣之間的關系，并且廣義擬陣的區(qū)間性深刻揭示了廣義擬陣的內在性質，其與平衡廣義擬陣、擬陣與反擬陣的交、廣義擬陣的分塊及廣義擬陣的圈都有很密切的關系(見文獻[2])。

定理2 一個偏序集區(qū)間廣義擬陣(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,ζ)為偏序集區(qū)間廣義擬陣當且僅當σ(B)?σ(A)∪σ(C)。

證明 若(P,ζ)為偏序集區(qū)間廣義擬陣，則?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,ζ)具有區(qū)間性質當且僅當若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,ζ)為偏序集區(qū)間廣義擬陣。

反過來,設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,ζ)具有區(qū)間性質矛盾。

3 偏序集廣義擬陣子廣義擬陣的區(qū)間性

區(qū)間性在廣義擬陣的研究中有很重要的作用，對廣義擬陣來說，其子廣義擬陣的區(qū)間性研究是有趣的，本節(jié)研究偏序集廣義擬陣的偏序集子廣義擬陣的區(qū)間性質。

定義5 設(P,ζ)為偏序集廣義擬陣，k∈N,定義ζk為

ζk={A∈ζ||A|≤k,A∈F(P)}。

容易證明(P,ζk)為偏序集廣義擬陣。稱(P,ζk)為k-截短偏序集廣義擬陣。

命題1 設(P,ζ)為偏序集區(qū)間廣義擬陣,(P,ζk)為k-截短偏序集廣義擬陣，則(P,ζk)具有區(qū)間性質。

證明 設(P,ζ)為一偏序集區(qū)間廣義擬陣,(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,ζ)為一偏序集區(qū)間廣義擬陣,以及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)具有區(qū)間性質。

定義6 設(P,ζ)為偏序集廣義擬陣，T為P的子濾子,定義ζT為

ζT={A∈ζ|A∈T}。

容易證明(T,ζT)為偏序集廣義擬陣。稱(T,ζT)為限制偏序集廣義擬陣。

與命題1的證明類似,我們有以下結論成立。

命題2 設(P,ζ)為偏序集區(qū)間廣義擬陣,(T,ζT)為限制偏序集廣義擬陣,則(T,ζT)具有區(qū)間性質。

定義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,ζ)為偏序集區(qū)間廣義擬陣,(P-B,ζ/B)為從(P,ζ)到P-B的收縮偏序集廣義擬陣,則(P,ζ/B)具有區(qū)間性質。

定義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)為偏序集區(qū)間廣義擬陣,則直和(P1∪P2,ζ1⊕ζ2)與序和(P1∪P2,ζ1?ζ2)具有區(qū)間性質。

以上研究了偏序集區(qū)間廣義擬陣的子擬陣的區(qū)間性質，下面給出一個偏序集區(qū)間廣義擬陣直立的區(qū)間性質。

設β為偏序集廣義擬陣(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,ζ)為偏序集區(qū)間廣義擬陣,(P,ζ′)為偏序集廣義擬陣(P,ζ)的直立,則(P,ζ′)具有區(qū)間性質。

證明 首先證明(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,ζ′)的區(qū)間性。

設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,ζ)為偏序集區(qū)間廣義擬陣，結論成立。若|C|=|D|,D∈β,則?x∈Max(P-C),有A∪x,C∪x∈ζ∩F(P),由于B?C,故B∪x∈ζ∩F(P)。

綜上,(P,ζ′)為偏序集區(qū)間廣義擬陣。

4 結語

本文研究了偏序集廣義擬陣區(qū)間性質,給出了偏序集區(qū)間廣義擬陣的3個等價刻畫,較為深刻地揭示了偏序集區(qū)間廣義擬陣的性質。隨后研究了偏序集區(qū)間廣義擬陣的子擬陣的區(qū)間性,得到了偏序集區(qū)間廣義擬陣的直立的區(qū)間性。這些結果豐富了偏序集廣義擬陣研究的內容,為進一步研究偏序集區(qū)間廣義擬陣的性質奠定了基礎。