[科普中國]-公共代表系

公共代表系(system of common representatives)是代表系的一種。設(shè)T集有兩個(gè)分拆：T=A?∪A?∪…∪Am，T=B?∪B?∪…∪Bm，其中Ai，Bj都不是空集(i，j=1，2，…，m)，若有T的一個(gè)m子集E滿足：Ai∩E≠?，Bj∩E≠?(i，j=1，2，…，m)，則這2m個(gè)非空交集都是1集，這樣的E稱為上面兩個(gè)分拆的公共代表系，簡稱SCR，上述兩個(gè)分拆有SCR的充分必要條件是：對任一整數(shù)k，1≤k≤m，以及對{1，2，…，m}的任一k子集{i?，i?，…，ik}，并集Ai?∪Ai?∪…∪Aik至多包含m個(gè)子集B?，B?，…，Bm中的k個(gè)1。

基本介紹設(shè)集合T分拆為m個(gè)子集2

其中

又有T的第二種分拆，

其中

若存在T的一個(gè)m元子集E，使

即存在E={ai|i=1，2，…，m}

則E為T的兩個(gè)分拆(1)和(42)的一個(gè)公共代表系(systems of common representatives)，簡寫為SCR。

公共代表系的存在性關(guān)于SCR存在性，有下列充分必要條件。

定理1 集合T的兩個(gè)分劃(1)和(2)具有SCR的充要條件是：對任一整數(shù)k=1，…，m以及任意k個(gè)子集，并集至多包含k個(gè)子集Bj(j=1，…，m)。

證明 對T的兩個(gè)分拆(1)和(2)，我們引進(jìn)它們的相交矩陣的概念。

如果有{1，2，…，m}上的兩個(gè)置換σ和τ，使

定義相交矩陣C=(Cij)，C是m階非負(fù)整數(shù)方陣，其中

顯然，這兩個(gè)分拆具有SCRC有m個(gè)非零元

且ρc=m不存在(m-k)×(k+1)零子矩陣(0≤k≤m-1)不存在m-k個(gè)Ai,它們的并集與k+1個(gè)Bj不交不存在k個(gè)Ai,它們的并集包含k+1個(gè)Bj任意k個(gè)Ai的并集至多包含k個(gè)Bj,k = 1,2,..,m，這就證明了定理。證畢。

系2 按定理1的條件及記號，T的兩個(gè)分拆(1)和(2)共有per C個(gè)SCR。

證明 C的m個(gè)非零元,i = 1,2,..,m,可產(chǎn)生個(gè)SCR。證畢。

系3 若集T的兩個(gè)分拆(1) 和(2),每個(gè)Ai和每個(gè)Bj都是r元子集，則兩分拆必有SCR。

證明 這是定理1 的特例。

至1996年，尚不知道三個(gè)集族有公共SCR存在的條件，甚至沒有一個(gè)接近的猜想2。

作為定理1的一個(gè)應(yīng)用，我們有

定理4 設(shè)G是一個(gè)不可交換的有限群，H為G之子群，并設(shè)

是G的一右陪集分解，且

是G的一左陪集分解，則必存在元∈G，使

本詞條內(nèi)容貢獻(xiàn)者為:

王海俠 - 副教授 - 南京理工大學(xué)