擬陣的獨立集構成的偏序集

(河北大學 數學與信息科學學院，河北 保定 071002)

雖然擬陣在組合理論中很重要[1-3]，但是這并不意味著擬陣可以覆蓋組合理論的所有方面。組合理論中的許多方面可以用擬陣清晰地解釋。這些解釋成為組合數學與更多數學主流領域的連接帶。將偏序集理論[4-5]應用到擬陣的研究是一條成功之路[1-3,6-14]。此外,借助于偏序集理論,可以建立與擬陣有關的一些新框架[6-7,14]。擬陣具有幾何格表示，反之，每個幾何格是簡單擬陣；但是并不是每個擬陣都是簡單的，即有些擬陣不能由幾何格給予特征。另外,Welsh[2]指出，擬陣最著名的算法性質與貪心算法有密切關系。貪心算法已被廣泛地應用和研究[1,2,15-16]。擬陣的貪心算法特征是由擬陣的獨立集所描述的[2]。為了尋找擬陣的更多算法特征，并將擬陣的應用范圍拓廣，考慮到每個格都是偏序集，因此，本文中考慮將貪心算法與偏序集結合，以用于挖掘擬陣的更多算法結果，該實現首先需要解決擬陣與偏序集之間的關系問題，才能進一步探索擬陣新的特征。在開始研究之前,應注意以下幾點。1)擬陣由其獨立集族所定義[1-3]。2)Boolean格已經用于研究任意基數集上的擬陣之獨立集的問題[17-19]。3)擬陣是一種特殊的獨立結構[20]。4)因為與獨立集有關,所以Boolean格已被用于擬陣的研究[14],另外，Mpi-空間和獨立空間可以分別用偏序集予以特征化[19,21]。偏序集理論與擬陣也有成功的結合[1-2,22]。5)對于任意擬陣M=(S,T(M))，其中S為有限集，T(M)為M的獨立集族,可以得到與該擬陣有關的偏序集(T(M),?)。

上述這幾點蘊含著用擬陣的獨立集對應的偏序集探討擬陣的必要性。本文中利用偏序集理論將擬陣特征化，該方法不同于已有的發現擬陣的特征的研究方法，例如，擬陣的幾何格特征的發現方法[1-3]。

為了使影響擬陣應用的幾何格條件減弱為更廣泛的數學結構——偏序集，本文中通過擬陣的獨立集族構建偏序集，用偏序集配合Boolean格搭建擬陣，在同構意義下實現用偏序集的性質將擬陣特征化。首先提出在一定條件下，偏序集P能在同構意義下定義擬陣M(P)；在同構意義下,挖掘滿足一定條件的偏序集與無環擬陣之間的關系，并將結果與著名的擬陣、幾何格之間的結果進行比較。

1 預備知識

1.1 符號

本文中所有討論均為有限。|A|為集合A的基數；2A為A的冪集；max{|Xi| ∶i=1,2,…,n<∞}為集合{|Xi| ∶i=1,2,…,n<∞}中的元關于自然序的最大值。

在偏序集P中，Max(P)是P中極大元集合；若x和y是P中不可比元，則記為x‖y。

∨和∧分別為格中的并和交2種運算。

1.2 定義

1)設S為有限集，T 為S的子集族。如果T 滿足以下條件，那么稱(S,T )為擬陣(matroid)，記為M=(S,T )，T 記為T (M)，其中的元稱為獨立集。

①?∈T。

②若X∈T且Y?X,則Y∈T。

③若U、V是T中的元且|U|=|V|+1,則存在x∈UV滿足V∪{x}∈T。

若S的子集X不屬于T,則稱X為M的相關集。M的基是M的極大獨立集。M的秩函數是函數ρ∶ 2S→，定義為ρ(A)=max{|X| ∶X?A,X∈T }，A?S。S的秩稱為擬陣M的秩，記為ρ(M)。[2]

2)擬陣M的環(loop)是S的元素x，若{x}為相關集；稱S的2個元x、y為平行的(parallel)，若它們均不是環，但是{x,y}為相關集。

稱無環、無平行元的擬陣為簡單擬陣(simple matroid)。

2個擬陣M1=(S1,T1)和M2=(S2,T2)稱為同構的(記為M1?M2)，如果存在雙射f∶S1→S2滿足A∈T1?f(A)∈T2。[2]

3)若偏序集P有唯一的最小元，通常將該元記為0,則將覆蓋0的元稱為原子(atom)。P的全序子集稱為P的鏈(chain)，即{x0,x1,…,xk}是一個鏈當且僅當x0

4)格L稱為Boolean的當且僅當L為含最小元以及最大元的有補分配格。[4]

2 偏序集與擬陣的獨立集

本節將研究擬陣的獨立集族由包含關系所構成的結構，并探討偏序集與擬陣之間的關系。這些關系的意義和價值在于它們可以將擬陣框架下的結果與偏序集框架下的內容相互轉化。

令M為S上的擬陣，T (M)為其獨立集族,B(M)為其基族。令P (M)代表(T (M),?)。

性質11)P (M)以{?}為其最小元。

2)P (M)的原子集是M中秩等于1的獨立集的全體。

3)a∈Max[P (M)]當且僅當a∈B(M)。

4)X在P (M)中覆蓋Y的充要條件是X,Y∈P (M),Y?X并且|X|=|Y|+1。

引理11)在P (M)中所有的極大鏈有相同的長|B|,此處B∈B(M)。

2)P (M)中的每個元素I以M的秩函數ρ(I)為其高度。

3)對于任意基B∈B(M),在P (M)中的區間[0,B]是Boolean格，此處0={?}。另外,對任意的I∈P (M),I是P (M)的一些原子的并。

4)對于任意的I,J∈P (M),如果|J|=|I|+1成立,那么存在j∈JI滿足I∪{j}∈P (M)。

證明：由M中基的定義以及M中秩函數的定義，易得1)、2)和4)。根據性質1中的3),可以導出B∈P (M)。對于任意的X?B，有X∈P (M)，因此，得到 (2B,?)?P (M)和(2B,?)=({Y∈T (M)∶Y?B},?)，從而,3)成立。引理1證畢。

引理1的3)表明Boolean格將會揭示偏序集與擬陣之間的一些內在關系。為了驗證該結論,需要下面的引理。

引理21)有限偏序集P有最小元0。設h為P的高函數,Θ為P中的原子集。對于x∈P，設Xx={a∈P∶a∈Θ且a≤x}。若P滿足如下條件2)— 4)，則存在定義在Θ上的滿足(T (M(P)),?)?P的擬陣M(P),并且M(P)無環。

3)對于任意b∈Max(P)，[0,b]?(2{y∈Θ ∶y≤b},?)成立。

4)對于任意z,t∈P,若h(t)=h(z)+1成立,則存在y∈XtXz滿足z∨y∈P和Xz∪{y}={a∈P∶a∈Θ且a≤z∨y}。

證明：根據條件1),h和Θ二者都有意義。設I(P)={X?P∶存在x∈P，使得X= {y∈P∶y是P的原子，并且y≤x} }。

首先證明(Θ,I(P))是擬陣。

由條件1)可知，0∈P成立，但是0不是原子。根據條件2)，這意味著?∈I(P)，因此,對于I(P),在1.2節1)中的條件①成立。

設U、V∈I(P)且|V|=|U|+1。根據I(P)的定義，可知u=∨U∈P且v=∨V∈P,另外,Xu=U和Xv=V成立。根據條件2)和|V|=|U|+1，得到h(v)=h(u)+1。利用條件4)可得y∈XvXu=VU滿足u∨y∈P和Xu∨y=U∪{y}。由此可知，U∪{y}∈I(P)，因此,在I(P)中,1.2節1)中的條件③成立。

根據擬陣的定義,(Θ,I(P))是擬陣。為了簡單起見,記(Θ,I(P))為M(P)。

證明(I(M(P)),?)?P。因為I(M(P))是I(P)，所以證明(I(P),?)?P。

事實上，易知I(P)={Xx∶x∈P}。

設x∈P。由條件2),有且僅有X∈I(P)滿足∨X=x；反之，若∨X=x,則X∈I(P)；因此，定義為x→Xx的映射φ∶P→I(P)是有意義的。根據I(P)的定義，對于x∈P，有I(P)={Xx∶φ(x)=Xx}。根據條件2)，φ為雙射。下面證明φ是同構。

容易得到a=0∈P的充要條件是φ(a)={?}。

設x,y∈P，則φ(x)=Xx=X={a∶a∈Θ且a≤x}且φ(y)=Xy=Y={a∶a∈Θ且a≤y}。

若x≤y，由條件2)可知x=∨X以及y=∨Y。根據x≤y可知，若a∈X,則a∈Y，因此X?Y。反之，設I,J∈I(P)且I?J，則根據條件2)和I(P)的定義可得，存在i,j∈P滿足i=∨I和j=∨J。另外，可以確定I={a∈Θ∶a≤i}且J={a∈Θ∶a≤j}。由i∈I?J可得i∈J，進而有i≤j，即x≤y當且僅當X?Y。

類似地,可以證明，在P中x‖y的充要條件是在I(P)中X‖Y，此處∨X=x且∨Y=y。

從而,φ是在P與(I(P),?)之間的同構映射。

證明M(P)無環。由于φ為雙射,因此x∈Θ?Xx={x}∈I(P)。由此可知，M(P)無環。引理2證畢。

通過分析引理2條件1)— 4)，發現如果一個偏序集不滿足條件1),則不存在擬陣M滿足(T (M),?)?P，即條件1)對引理2而言是必需的。

定理1有限偏序集P同構于一個擬陣的獨立集族所構成的偏序集當且僅當P滿足引理2中的條件1)— 4)。

證明:由引理1、2容易得到所需結論。定理1證畢。

一個擬陣的結構并不能夠由其獨立集的偏序集完全定義。對于不同構的2個擬陣,它們的獨立集的偏序集可同構。如令M1=({1,2},T(M1)={?,{1}})而M2=({1},T(M2)={?,{1}})，可得(T (M1),?)=(T (M2),?)而M1M2。原因是M1中有環。事實上,{2}是M1的環，而M2是無環的。

無環擬陣的重要性體現在定理2中。

定理2有限偏序集P與以P為原子集的擬陣M(P)之間的對應是滿足引理2中的條件1)— 4)的有限偏序集構成的集合與無環擬陣構成的集合之間的雙射。

證明：若P為滿足引理2中的條件1)— 4)的偏序集，則由引理2,可知M(P)為無環的擬陣，并且在同構意義下P (M(P))是P。反之，如果對于無環的擬陣M，P (M)是其獨立集族,那么利用在引理2中M(P (M))的構造和P (M)的結構,可以導出M(P (M))?M。定理2證畢。

根據定理2，對于無環的擬陣的研究即為對滿足引理2中的條件1)— 4)的有限偏序集的研究。如果重點研究無環的擬陣，那么擬陣中許多有趣問題可以在偏序集中延續。此外,在同構意義下,無環擬陣可以由滿足引理2中的條件1)— 4)的偏序集將其特征化。

根據引理1、2，再結合定理2,可以得到簡單擬陣的一個重要結果。

推論1由Boolean格P到以P為原子集的擬陣M(P)上的映射是有限Boolean格集合與擁有唯一基的簡單擬陣集合之間的雙射。

將擬陣的一些結果轉化到偏序集的框架下的內容是很有必要的。

定理3若M=(S,T )為擬陣,k∈且0≤k,Tk={X∶X∈T,|X|≤k}，那么(S,Tk)為擬陣。

反之，令M2=(S2,T2)為擬陣。若S3=S2∪{b}且T3=T2成立，則M3=(S3,T3)為擬陣并且{b}是該擬陣的環。在下面的證明中僅需要考慮無環的擬陣。

令M無環。由定理2可確定偏序集P (M)即(T,?)是對應于M的。根據性質1中的1)— 4)和引理1中的1)— 4)可知，P (M)以S為原子集并且滿足引理2中的條件1)— 4)。

令h為P (M)的高函數，并且對x∈P (M)有Xx={a∈P (M)∶a≤x且a∈S}。由引理2中的2)可知x=∨Xx。

令P (M)k={x∈P (M)∶h(x)≤k}。根據引理1的2),可知P (M)k={x∈P (M)∶ρ(x)≤k}= {x∈P ∶|x|≤k}，因此P (M)k=Tk成立。

下面證明P (M)k滿足引理2中的條件1)— 4)。

容易得知P (M)k滿足引理2中的條件1)和4)。

若b∈Max[P (M)k]，則a∈Max[P (M)]滿足b≤a。在P(M)中,由引理2中的條件3),可以得到[0,a]是Boolean格并且滿足[0,a]?(2{y∈S ∶y≤a},?)，即[0,b]為Boolean格且[0,b]?(2{y∈S ∶y≤b},?)，從而在P(M)k的區間[0,b]k表現在P(M)中是區間[0,b]，因此，[0,b]k為Boolean格并且[0,b]k?(2{y∈S ∶ y≤b},?)，即對于P(M)k,引理2中的條件3)是成立的。

根據定理1、2，可以得到M(P(M)k)?(S,Tk)。即(S,Tk)為擬陣。定理3證畢。

定理3與文獻[18]中定理1的結果是相同的，但是得到結果的方法不同。這表明本文中的方法是成功的。

3 總結

文獻[20]中的定理2只有簡單擬陣才能夠滿足,但是本文中的定理2對于任何無環的擬陣都適用。因為一個簡單擬陣一定是無環的并且無平行元，所以本文中的定理2比文獻[20]中定理 2的適用范圍廣。由此可知，本文中的主要結果即定理2拓廣了擬陣已有的結果。事實上，本文中的思想不僅可用于擬陣的其他公理體系結合另外的數學結構，將擬陣特征化，而且也為使更多算法應用于擬陣領域、擴大擬陣的適用范圍奠定了理論基礎。

在今后的研究中將借助于偏序集理論和貪心算法揭示擬陣更多的性質，并將其應用到更廣的范圍，例如,利用擬陣和貪心算法尋找概念格的結構。