【摘要】：本論文考慮了極值組合與編碼理論中的若干問題。通過使用包括多項式方法、超圖移除引理、加法數(shù)論在內(nèi)的強有力的數(shù)學(xué)工具,研究了若干個具有相當難度的猜想和公開問題。在第二章中,我們考慮了組合群試領(lǐng)域內(nèi)由Erdos,Frankl和Furedi提出的、具有三十年歷史的一個猜想。給定n個被測樣本,其中最多有d個是陽性的,群試理論的目標是采用盡可能少的測試次數(shù)找到所有陽性樣本,而不是僅僅對所有樣本進行逐個檢測。一個二元矩陣被稱為是d-分離的,如果它的任意d列的布爾和都不包含其它列。分離矩陣在非自適性群試中有著極為重要的應(yīng)用。用T(d)表示最小的t,使得存在一個滿足n t × rn的d-分離矩陣。前人已證明T(?)并猜測T(d)≥ (d+1)2。通過技巧性地利用Erdos和Gallai經(jīng)典的圖匹配定理,我們證明(?),縮小了與猜想值之間的鴻溝。在第三章中,我們考慮了防誣陷碼、父代識別碼與追蹤碼的上界。這些碼都是被用來保護具有版權(quán)的數(shù)字文件的。它們在諸如數(shù)字指紋、廣播加密方案等場景中都有應(yīng)用。利用一些組合計數(shù)方法中的技巧,我們分別給出了這三種碼的上界。這些界都是目前已知的最優(yōu)界。在第四章中,我們研究了一個重要的圖蘭問題,即Brown, Erd6s和S6s提出的稀疏超圖問題�？紤]n個頂點上的r-均衡超圖,設(shè)其不含僅由v個頂點張成的e條邊,四十多年前,Brown等人用函數(shù)fr(n,u,e)來表示這個超圖所能含有的最大邊數(shù)。他們提出了一個著名猜想:(?)對所有整數(shù)r k ≥ 2,e ≥ 3都成立。注意到,當r=3,e = 3,k = 2時,該猜想的正確性是由著名的Ruzsa-Szemeredi的(6,3)-定理所保證的。我們?yōu)樵摬孪氲某闪⑻峁┝烁嗟淖C據(jù)。一方面,我們用超圖移除引理證明:猜想的右邊對所有固定的整數(shù)r ≥ k + 1 ≥ e ≥ 3都成立。我們的結(jié)果涵蓋了歷史上達到猜想上界的所有已知情形。另一方面,通過構(gòu)造一個合適的加法數(shù)論中的sum-free集,我們說明:猜想的左邊對r≥3,k = 2與e = 4,5,7,8都成立。在e≥4且r≥ 4的范圍內(nèi),我們的構(gòu)造是第一個使猜想下界成立的構(gòu)造�？煞止Ｗ迨且环N非常有用的組合結(jié)構(gòu),它是組合學(xué)、密碼學(xué)和編碼理論中很多研究對象的推廣。在第五章中,我們解決了關(guān)于可分哈希族和完美哈希族的上下界的若干公開問題和猜想。首先,我們發(fā)現(xiàn)可分哈希族的大小滿足一種Johnson型的迭代不等式。從此出發(fā),我們給出了可分哈希族的改進上界。其次,我們構(gòu)造了一類完美哈希族的無窮類。它不僅正面回答了 Bazrafshan和Trung關(guān)于可分哈希族的一個公開問題,而且回答了 Alon和Stav關(guān)于父代識別碼的一個猜想。最后,用表示(N,q)表示q元N長強度為t的完美哈希族的最大可能大小。Walker和Colbourn猜測當q充分大時有p3(3,q) = o(q2)。通過使用(6,3)-定理,我們證明了(?)。此外,利用一些加法數(shù)論的工具,我們還證明了(?)。在第六章和第七章里,我們分別研究了信息科學(xué)中的兩個編碼問題。第一個問題是集中式緩存編碼方案,它是由Maddah-Ali和Niesen提出的一種技術(shù),被用來降低無線網(wǎng)絡(luò)系統(tǒng)中高峰時期的網(wǎng)絡(luò)負載。設(shè)K是系統(tǒng)中用戶的數(shù)目,則比率R(K)和復(fù)雜性F(K)是緩存方案的主要衡量指標。我們希望設(shè)計使R(K)和F(K)都盡量小的緩存方案。之前的結(jié)果都滿足R(K)是常數(shù)而F(K)是指數(shù)函數(shù)。我們把這個問題與3-均衡3-部的(6,3)-free的超圖的構(gòu)造聯(lián)系起來,并提出了第一個具有常數(shù)比率、亞指數(shù)復(fù)雜性的緩存方案。第二個問題是分布式存儲碼,它在現(xiàn)代存儲系統(tǒng)中有著重要應(yīng)用。Piggybacking設(shè)計被用來構(gòu)造同時具有好的譯碼復(fù)雜性與修復(fù)帶寬的存儲碼。通過引入一個新穎的piggybacking框架,我們所提出的piggyback碼具有與現(xiàn)存的碼相同的譯碼復(fù)雜性,但是使修復(fù)帶寬率從r-1降低到了(?)。在第八章中,我們考慮了一個有限域上的極值問題。最近,Croot-Lev-Pach和Ellenberg-Gijswijt使用了一種新穎的多項式方法,分別界定了Z4n與F3n上不含3長等差數(shù)列的最大子集的大小,這兩篇文章都發(fā)表在《Annals of Mathematics》上。Terence Tao總結(jié)了他們的工作,把其提煉為一種計算某些多變量函數(shù)的秩的方法。我們改變了Tao的計數(shù)公式,并用新公式來證明了如下結(jié)論:設(shè)q是一個固定的奇素數(shù)冪,A為Fqn的子集,使得不存在三個不同的元素x，，y,z∈A滿足
[Abstract]:Some problems in the theory of extreme combination and coding are considered in this paper. By using the powerful mathematical tools, including the polynomial method, the super-graph removal approach and the addition number theory, several conjecture and open problems with considerable difficulty are studied. In the second chapter, we consider a conjecture of the three-year history of Erdos, Franklin and Furedi in the field of cluster test. Given n of the n-tested samples, where d is positive, the objective of the group test theory is to find all positive samples using as few test times as possible, rather than just one-by-one detection of all samples. A binary matrix is called d-separated, and if its arbitrary d column does not contain other columns. The separation matrix has very important application in the non-self-adaptive group test. the minimum t is represented by t (d) so that there is a d-separation matrix that satisfies n t-rn. T (?) and guesses t (d) 1 (d + 1) 2. By using the graph matching theorem of Erdos and Galai, we prove (?), the gap between the conjecture value is reduced. In chapter 3, we consider the upper boundary of the anti-frame code, the parent identification code and the tracking code. these codes are used to protect digital files with copyright. They are applied in scenarios such as digital fingerprints, broadcast encryption schemes, and the like. Using the techniques of some combination counting methods, we give the upper bounds of these three codes, respectively. These boundaries are the best known in the art. In the fourth chapter, we have studied an important problem of Tulane, that is, the problem of the sparse hypergraph proposed by Brown, Erd6s and S6s. In consideration of the r-equilibrium hypergraph on n vertices, it is assumed that it does not contain the e-edge only by v vertices, and for more than forty years, Brown and others use the function fr (n, u, e) to represent the maximum number of edges that can be included in this hypergraph. They made a famous guess: (?) All integers r k, 2, e and 3 are established. It is noted that when r = 3, e = 3, k = 2, the correctness of the conjecture is guaranteed by the (6, 3)-theorem of the well-known Ruzsa-Szemeteredi. We have provided more evidence for the establishment of the conjecture. On the one hand, we removed the lemma from the hypergraph: the right-hand side of the conjecture is set up for all fixed integers, r-kk + 1 and e-3. Our results cover all the well-known scenarios in history that have assumed the bounds of the conjecture. On the other hand, by constructing a sum-free set in a suitable number theory, we note that the left pair r = 3, k = 2 and e = 4, 5, 7, and 8 of the conjecture are all set up. In the range of e-4 and r-4, our structure is the first to set up the lower bound of the conjecture. The distributable hash family is a very useful combination structure, which is a generalization of many research objects in the theory of combination, cryptography and coding. In the fifth chapter, we have solved a number of open questions and conjecture on the upper and lower bounds of the sub-hash family and the perfect hash family. First, we find that the size of the sub-hash family satisfies a Johnson-type iterative inequality. From this point of view, we give the improved upper boundary of the sub-hash family. Second, we construct an infinite class of perfect hash family. It's not only a positive answer to Bazrafshan and Trung's open question about the partible-hash family, but also an answer to Alon and Sta's conjecture about the parent's identification code. Finally, the maximum possible size of the perfect hash family, denoted by (N, q), of the q-element N long-intensity of t is denoted by (N, q). Walker and Colboun guesses that there are p3 (3, q) = o (q2) when q is sufficiently large. By using (6, 3)-theorem, we prove (?). In addition, using some of the tools of the addition number theory, we also prove (? In Chapter 6 and Chapter 7, we respectively study the two coding problems in the information science. The first problem is a centralized cache coding scheme, a technique proposed by Maddah-Ali and Niesen, which is used to reduce the network load in the high-peak period in the wireless network system. If K is the number of users in the system, the ratio R (K) and the complexity F (K) are the main measure of the cache scheme. We want to design a cache that makes both R (K) and F (K) as small as possible. The previous results satisfy the constant of R (K) and F (K) is an exponential function. We associate this problem with the construction of 3-balanced 3-part (6, 3)-free hypergraph, and put forward the first cache scheme with constant ratio and subexponential complexity. The second problem is the distributed storage code, which has an important application in modern storage systems. the piggy back design is used to construct a memory code that has good coding complexity and repair bandwidth at the same time. By introducing a novel piggy back frame, our proposed piggy back code has the same decoding complexity as the existing code, but reduces the repair bandwidth rate from r-1 to (?). In Chapter 8, we consider the extreme problem on a finite field. Recently, Cot-Lev-Pach and Elenberg-Gijswjt use a novel polynomial method, which respectively defines the size of the largest subset of the three-length equal-difference series on the Z4n and F3n, both of which are published in the . Terrence Tao summed up their work and refined it as a method of calculating the rank of certain multivariate functions. We change the Tao's counting formula and use the new formula to prove the following conclusion: Let q be a fixed odd prime power, A is a subset of Fqn, so that there are no three different elements x, y, z and A.
【學(xué)位授予單位】：浙江大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2017
【分類號】：O157

【相似文獻】

相關(guān)期刊論文 前10條

1 王建方,閆桂英;超圖的圈結(jié)構(gòu)[J];科學(xué)通報;2001年19期

2 林啟忠,房杰,劉娟,杜智華;兩類特殊超圖的分數(shù)橫貫[J];新疆師范大學(xué)學(xué)報(自然科學(xué)版);2005年03期

3 唐宇軒;;圈區(qū)間超圖相關(guān)性質(zhì)的討論[J];新疆師范大學(xué)學(xué)報(自然科學(xué)版);2006年03期

4 劉木伙;柳柏濂;;嚴格(d)-連通無圈超圖的計數(shù)[J];數(shù)學(xué)學(xué)報;2007年06期

5 范新愛;趙守娟;;r一致導(dǎo)出匹配可擴張超圖及性質(zhì)[J];新鄉(xiāng)學(xué)院學(xué)報(自然科學(xué)版);2009年05期

6 石怡;王福;;有關(guān)交簇超圖的兩個結(jié)論[J];兵團教育學(xué)院學(xué)報;2009年05期

7 朱俊杰;;超圖的奇圈橫貫[J];成都大學(xué)學(xué)報(自然科學(xué)版);2010年02期

8 孫林;;完美圖在超圖上的推廣[J];新疆師范大學(xué)學(xué)報(自然科學(xué)版);2011年01期

9 王福;石怡;杜智華;;一類超圖的橫貫[J];石河子大學(xué)學(xué)報(自然科學(xué)版);2011年03期

10 趙凌琪;馮偉;徐春雷;吉日木圖;;無圈超圖規(guī)模的進一步研究[J];應(yīng)用數(shù)學(xué)學(xué)報;2012年05期

相關(guān)重要報紙文章 前10條

1 本報駐東京記者 吳仲國;中國軟件在日本叫響知名品牌成市場寵兒[N];科技日報;2002年

2 證券時報記者 吳中珞;超圖軟件信披創(chuàng)新 微博釋疑股吧發(fā)帖詳解年報延期[N];證券時報;2011年

3 本報記者 朱熹妍;地理信息火爆 超圖地理專注成器[N];經(jīng)濟觀察報;2008年

4 記者 趙一蕙;超圖軟件業(yè)績快報“失準”逾20%[N];上海證券報;2013年

5 欒玲　趙培;超圖軟件：中國“智”造的跨國軟件企業(yè)[N];中國高新技術(shù)產(chǎn)業(yè)導(dǎo)報;2010年

6 本報記者 解佳濤　戈清平;超圖軟件：做“中國智造”的跨國軟件企業(yè)[N];中國高新技術(shù)產(chǎn)業(yè)導(dǎo)報;2010年

7 本報記者 梁爽;超圖：十年打造地理信息超級版圖[N];中國政府采購報;2012年

8 徐洋;北京市委書記郭金龍視察超圖軟件公司[N];中國測繪報;2012年

9 本報記者 鄭燃;超圖軟件：讓應(yīng)急事件避免盲人摸象[N];政府采購信息報;2011年

10 江雪;鐘耳順鐘情GIS[N];中國企業(yè)報;2007年

相關(guān)博士學(xué)位論文 前10條

1 上官沖;極值組合與編碼理論中的若干問題[D];浙江大學(xué);2017年

2 古萬榮;基于超圖模型的新聞推薦研究[D];華南理工大學(xué);2015年

3 孫艷萍;3一致超圖的拉格朗日和最大團之間的關(guān)系的研究[D];湖南大學(xué);2016年

4 彭豪;超圖的Motzkin-Straus型結(jié)果及Frankl-F(?)redi猜想[D];湖南大學(xué);2015年

5 岳俊杰;超圖H譜理論和稀疏低秩優(yōu)化算法研究[D];清華大學(xué);2016年

6 吳艷;3-一致超圖分解及相關(guān)問題[D];北京交通大學(xué);2010年

7 吳穎敏;市場機遇發(fā)現(xiàn)的超圖支持方法研究[D];華中科技大學(xué);2009年

8 葉淼林;圖與超圖理論中的譜方法[D];安徽大學(xué);2010年

9 吉日木圖;圖的標號及超圖分解問題研究[D];大連理工大學(xué);2006年

10 王琦;網(wǎng)絡(luò)中的超圖嵌入問題[D];山東大學(xué);2007年

相關(guān)碩士學(xué)位論文 前10條

1 朱俊杰;超圖的奇圈橫貫和偶邊著色[D];新疆師范大學(xué);2008年

2 程全勝;超圖路徑求解算法及其應(yīng)用[D];華中科技大學(xué);2008年

3 趙金輝;超圖的圈性[D];上海交通大學(xué);2011年

4 范新愛;關(guān)于一致超圖的導(dǎo)出匹配可擴張性[D];新疆師范大學(xué);2006年

5 林啟忠;超圖中的C-圈[D];新疆師范大學(xué);2006年

6 劉相國;超圖及其線圖的若干性質(zhì)的討論[D];內(nèi)蒙古師范大學(xué);2008年

7 張娜;兩類存取結(jié)構(gòu)及其信息率的研究[D];陜西師范大學(xué);2015年

8 彭茜茜;關(guān)于一致超圖的譜半徑[D];安徽大學(xué);2015年

9 李冠儒;完全3-一致超圖的分解及其應(yīng)用[D];內(nèi)蒙古民族大學(xué);2015年

10 伊國華;一致超圖的張量譜性質(zhì)研究[D];福州大學(xué);2014年

本文編號：2408890