基本介紹
- 中文名：擬剩餘設計
- 外文名：quasi-residual design
- 所屬學科：數學
- 所屬問題：組合學（組合設計）
基本介紹,相關定理,
基本介紹
定義1 若v,k與λ滿足條件λ(v-1)=k(k-1)，設D*為一個B(k-λ，λ；v-k)，則稱D*為一個擬剩餘設計(quasi residual design)。
討論下面這個問題是有意義的：設D*為一個B(k-λ，λ；v-k)，它是一個擬剩餘設計，是否存在一個SB(k，λ；v)使D*作為它的剩餘設計?試看下述例子，它實際上給出了當λ=1時從擬剩餘設計構作相應的對稱設計的一個重要方法。
例1 設V=Z16，D*=(V*，B*)為如下B(4，1；16)：
P1：{0，1，2，3}，{4，5，6，7}，{8，9，10，11}，{12，13，14，15}；
P2：{0，4，9，13}，{1，5，10，14}，{2，6，11，15}，{3，7，8，12}；
P3：{0，5，11，12}，{1，4，8，15}，{2，7，9，14}，{3，6，10，13}；
P4：{0，6，8，14}，{1，7，11，13}，{2，4，10，12}，{3，5，9，15}；
P5：{0，7，10，15}，{1，6，9，12}，{2，5，8，13}，{3，4，11，14}.
這是一個擬剩餘設計，並且是可分解的。它的平行類為Pi，i=1，2，3，4，5，用添加5個無窮遠點及一條無窮遠直線(即由這些無窮遠點組成的新區組)來構作所需的SB(5，1；21)，設1≤i≤5。對Pi中的每一個區組都添加一個無窮遠點
之後當作新區組，然後再添加一個新區組
，故共得21個區組，由於每一個無窮遠點與Z16中每一個元素都恰好相遇一次。任意兩個不同的無窮遠點也正好相遇一次。因此得到一個SB(5，1，21)。它以D*作為剩餘設計。
利用上面的方法可以證明下述定理。
相關定理
定理1 λ=1的任一擬剩餘設計都可以作為某個對稱設計的剩餘設計。
為證明上述定理，需要下面引理。
引理1 每一個λ=1的擬剩餘設計都是可分解的。
證明 設D*為一個擬剩餘設計B(k-λ，λ；v-k)，令n=k-1。由k(k-1)=v-1得v=n2+n+1，即v-k=n2，因此D*是一個B(n，1；n2)，它共有b=n(n+1)個區組。並且每一點都恰好包含在n+1個區組中，設A1為D*的一個區組，它的每一點都恰好包含在A1之外的n個區組中，並且A1中任意不同的兩點不可能同時包含在A1之外的任意區組中。否則將與λ=1矛盾，由於A1中共有n個點，因此恰有n2個區組與A1相交，並且交點唯一，從而恰有n-1個區組與A1不相交，設為A2，A3，…，An，下面證明A1，A2，…，An組成一個平行類。
對2≤i≤n，Ai中的任一點都必須與A1中的每一點都相遇一次，又因Ai中任意兩個不同的點都不可能在Ai之外的任意一個區組中相遇，從而與A1相交的n2個區組中的每一個都與Ai相交，於是A1，A2，...，Ai-1，Ai+1，…，An中的每一個都與Ai不相交，因此A1，A2，…，An組成一個平行類，記為P1。
設An+1為一個不屬於P1的區組，將n-1個與An+1不相交的區組記作An+2，…，A2n。由於An+1與P1中的每一個區組都相交，因此這n-1個區組都不屬於P1。同前可證An+1，An+2，…，A2n組成一個平行類，記作P2，P2與P1顯然不相交即沒有公共區組。一般地。設s≤n，已得到s個互不相交的平行類P1，…，Ps，則在剩下的(n+1-s)·n個區組中必可找到n個互不相交的區組Asn+1，Asn+2，…，A(s+1)n，它們組成一個平行類Ps+1，從而可將D*的全部n(n+1)個區組劃分成n+1個平行類，即D是一個可分解設計。
定理1的證明：設D*=(V*，B*)為λ=1的擬剩餘設計，則必有正整數n使D*為一個B(n，1；n2)。由引理2，D*的全部區組可劃分成n+1個平行類P1，P2，…，Pn+1。設1≤i≤n+1，對Pi中每一個區組都添加一個無窮遠點
作成新的區組，再將”無窮遠直線”
也看作一個區組，如此共得n2+n+1個區組,它們組成V=V*∪上的一個SB(k,1；v),此處k=n+1,v=n2+n+1，顯然D*是這個對稱設計的一個剩餘設計。
當λ=2時，M.Hall與W.S.Connor證明了下面的定理。
定理2 設λ=2，則每一個擬剩餘設計都是某個對稱設計的剩餘設計。
然而當λ≥3時，類似的結論未必成立，即使在λ=3時，也並不是每一個擬剩餘設計都可以作為某個對稱設計的剩餘設計的。
van Lint，Tonchev與Landgev構作出一個B(10，5；28)，這是一個擬剩餘設計。SB(15，5；43)不存在，由此給出了第一個這樣的例子，即使SB(k，λ；v)不存在，擬剩餘設計B(k-λ，λ；v-k)仍然存在。
