《三個組合問題的研究》是依託南京師範大學，由曹海濤擔任項目負責人的面上項目。
基本介紹
- 中文名：三個組合問題的研究
- 項目類別：面上項目
- 項目負責人：曹海濤
- 依託單位：南京師範大學
項目摘要,結題摘要,
項目摘要
本項目的研究對象主要為準支架、填充設計和組合分組測試，它們不僅在理論研究中有重要的地位，而且在通信和計算機等領域中有很強的套用背景。以等重量碼為背景的準支架是兩類經典組合設計（可分解的可分組設計和支架）的一般推廣形式，其研究可以促進它們的有機統一。可分解的填充設計可以用來構造密碼學中的門限方案。組合分組測試的思想方法在血液檢驗、數字指紋、分子生物等領域都有重要套用。在已有工作基礎上，本項目將系統研究區組大小為3和4的準支架的存在性問題；組大小一致的圈支架的存在性問題；部分可分解填充設計的存在性問題；還將研究分組測試和數字指紋之間的組合構造和算法，嘗試將分組測試的思想方法套用於其他領域。以上這些問題是組合數學中的重點研究對象，受到國內外學者的普遍關注，需要方法和技術上的突破。通過本項目的實施，不僅能豐富組合數學自身的理論成果，也可促進組合數學和信息等其他學科之間的交叉。
結題摘要
本項目主要研究組合設計理論中帶可分解性質設計的存在性問題以及在編碼和密碼中有重要套用的離散組合結構的存在性問題。這些問題大都是組合及相關領域專業雜誌上的公開問題。我們在這些公開問題的研究中取得了一些突破，主要成果如下。在經典設計的存在性方面，完全解決了圈長為任意整數的圈支架的存在性問題（1987年JCT（A）上的公開問題）。解決了圈長為任意奇數的幾乎可分解圈設計的存在性問題（2010年Combinatorica上的公開問題），同時也解決了一些圈長為偶數的情形。將幾乎可分解設計運用於著名的Hamilton-Waterloo問題的研究，對圈長為{3,4},{3,5},{3,7}的情形，完全解決了HWP解的存在性；對圈長都為奇數的情形, 大大推進了HWP解的存在性研究；幾乎解決了圈長含8的Hamilton-Waterloo問題的解的存在性問題。完全解決了區組大小為3的準支架設計的存在性問題（2013年JCD上的公開問題），統一了區組大小為3的可分解GDD和Frame的存在性結果。完全解決了組型一致的爪支架的存在性問題。徹底解決了子圖為爪的最大填充和最小覆蓋的存在性問題。完全解決了任意相遇數的組型一致的3-GDD大集的存在性問題，並得到相應simple 3-GDD的存在性問題。完全解決了對稱帶洞拉丁方大集的存在性問題。在以編碼和密碼為套用背景的離散組合結構的研究方面，關於二元二值自相關序列問題，當周期模4餘1時，部分解決了Schmidt 的猜想（2017年DCC上的公開問題）；當周期模4餘2時，解決了前人遺留的3個例外；同時得到一些二元二值自相關序列的不存在性結果。在以光正交碼為背景的循環設計的研究中，完全解決了n維奇數階循環填充設計的存在性問題；得到了若干變重量光正交碼的存在性結果。關於GSEDF問題，證明了不存在3個子集的GSEDF；給出了一些SEDF的不存在結果；用組合方法給出了GSEDF的第一個遞歸構造並由此得到一些存在性結果。對小參數的情形，給出了一些最優的可分Hash族；對一般情形，改進了一些最優的可分Hash族的上下界。對在網路快取中有重要套用的PDA的研究中，利用組合方法給出了PDA的一些構造，並給出界的猜想。
