組合設計的大集.pdf

1、設X是一個有限集.X上的一個循環(huán)三元組〈x，y，z〉是指由X中的三個有序對(x，y)，(y，z)和(z，x)構成的集合.X上的一個可遷三元組(x，y，z)是指由X中的三個有序對(x，y)，(y，z)和(x，z)構成的集合.一個v階的有向三元系是一個對子(X，B)，其中X是一個v元集，B是X上一些循環(huán)或可遷三元組(稱為區(qū)組)的集合，并且X中的任意有序對恰好屬于B的一個區(qū)組.特別地，如果B中的區(qū)組都是循環(huán)的(或可遷的)，則(X，B)叫做Me

2、ndelsohn(或可遷)三元系，并記作MTS(v)(或DTS(v)). 設(X，A)是一個MTS(v)，如果〈a，b，c〉∈A蘊涵〈c，b，a〉(∈)A，則此設計叫做純的，并記作PMTS(v).類似地，一個純的DTS(v)(簡記作PDTS(v))(X，A)是一個這樣的DTS(v)，(a，b,c)∈A蘊涵(c，b，a)(∈)A. 如果MTS(v)或DTS(v)的區(qū)組集能夠劃分成若干個子集，每個子集包含X的每個元素恰好一次

3、，則稱此設計為可分解的.可分解的MTS(v)與可分解的DTS(v)分別記為RMTS(v)及RDTS(v). MTS(v)(或DTS(v))的大集，記作LMTS(v)(或LDTS(v))，是v元集X上v-2個MTS(v)(或3(v-2)個DTS(v))的集合，并使得X上任意循環(huán)(或可遷)三元組作為區(qū)組恰好出現(xiàn)于一個MTS(v)(或DTS(v))之中.LPMTS(v)(或LPDTS(v))表示一個LMTS(v)(或LDTS(v))，

4、其中每個MTS(v)(或DTS(v))都是純的.LRMTS(v)(或LRDTS(v))表示一個LMTS(v)(或LDTS(v))，其中每個MTS(v)(或DTS(v))都是可分解的. MTS(v)的超大集，記作OLMTS(v)，是一個集合{(X\{x}，Bx)∶x∈X}，其中X是v+1元集，(X\{x}，Bx)是MTS(v)，并且Ux∈XBx正好包含X上所有循環(huán)三元組.OLPMTS(v)表示一個OLMTS(v)，其中每個MTS(

5、v)都是純的. 1850年，Kirkman在《Lady'sandGentleman'sDiary》中提出了一個問題：十五個女生排成三列出去散步，能否在一周內使得任意兩人不在同一行出現(xiàn)兩次?這個問題實際上是要尋找一個15階的Kirkman三元系KTS(15).Kirkman十五女生問題提出之初，Sylvester進一步提出：15元集合上的455個3-子集能否劃分成13個KTS(15)? Sylvester十五女生問題是數(shù)學

6、史上第一類大集問題，激發(fā)了許多專業(yè)人士與業(yè)余愛好者的興趣.自此之后各種各樣的大集問題相繼被提出與研究.1983至1984年，我國數(shù)學家陸家羲為解決Steiner三元系大集問題做出了突出的貢獻.到目前為止，LSTS，LMTS及LDTS的存在性問題已完全解決，而LPMTS，LPDTS，LKTS，LRMTS及LRDTS的研究結果卻很少. 本文研究組合設計的大集問題，諸如LPMTS，LPDTS，LRMTS及LRDTS. Benn

7、ett，Kang，Lei及Zhang給出了LPMTS的一些遞歸構造，并證明了LPMTS(12k)及LPMTS(12k+4)是存在的.田子紅應用類似的方法，給出了關于LPDTS的遞歸構造，證明了LPDTS(6k)及LPDTS(6k+4)的存在性.本文采用新的得力遞歸構造，結合必要的直接構造，徹底解決了LPMTS及LPDTS的存在性問題. LRMTS及LRDTS的存在結果非常有限.若v為奇數(shù)，LRMTS(v)及LRDTS(v)的大部

8、分結論從LKTS(v)得到，而LKTS(v)的存在性問題亦尚未解決.這些問題還需要更多技巧.本文給出了LRDTS的一個三倍構造，給出了LRMTS及LRDTS的乘積構造，建立了幾個新的無窮類. 論文的主要結果總結如下： (1)當且僅當v≡0，1(mod3)且v≥4時存在LPDTS(v). (2)當且僅當v≡0，1(mod3)，v≥4且v≠6，7時存在LPMTS(v). (3)對下列階數(shù)v存在LRMTS(v)

9、及LRDTS(v)：v=3nm(2·kn11+1)(2·kn22+1)…(2·kntt+1)，其中n≥1，t≥0，ni≥1，ki∈{7，13}(i=1，2，…，t)，m∈{1，4，5，7，11，13，17，23，25，35，37，41，43，47，53，55，57，61，65，67，91，123}∪{(7k+2)/3，(13k+2)/3，(25k+2)/3，22k+125j+1∶k≥0且j≥0}. 全文分為五章. 第一章

10、本章為引言，回顧了大集問題的歷史背景，介紹了相關問題的進展，列出了本文的主要方法及結果. 第二章本章確定了LPDTS的存在譜.首先引入t-純可劃分的可遷燭臺系(簡記作t-PPDCS)的概念，給出了用0-PPDCS構造LPDTS的方法.接著，利用s-fan設計給出了t-PPDCS的遞歸構造.然后通過一些輸入設計的直接構造，確定了LPDTS(6k+3)，LPDTS(12k+7)及LPDTS(12k十1)的存在性.最后LPDTS的存在

11、譜完全確定. 第三章本章確定了LPMTS的存在譜.一方面，首先類似于第二章，列出了LPMTS及t-PPMCS的遞歸構造.然后直接構造了1-PPMCS(63∶4)及0-PPMCS(63∶3)，從而確定了LPMTS(12k十9)及LPMTS(12k十1)的存在性.另一方面，對于奇數(shù)v≥7，建立了從LPMTS(v)及OLPMTS(v)到LPMTS(2v+1)的特殊構造.最終確定了LPMTS的存在譜. 第四章本章建立了LRDTS

12、的三倍構造.首先引入了雙可遷的可分解冪等擬群(簡記作DTRIQ)的概念.然后證明當且僅當3|v且v≠2(mod4)時存在DTRIQ(v).最后建立了從LRDTS(v)及DTRIQ(v)到LRDTS(3v)的三倍構造，同時得到了一個偶數(shù)階的無窮類，LRDTS(4·3n). 第五章本章建立了LRMTS及LRDTS的乘積構造.證明了若存在LRMTS(u)(或LRDTS(u))，TRIQ(u)(或DTRIQ(v))及LR(v)(Lei引