极值组合与编码理论中的若干问题

发布时间：2019-01-14 16:48

【摘要】：本论文考虑了极值组合与编码理论中的若干问题。通过使用包括多项式方法、超图移除引理、加法数论在内的强有力的数学工具,研究了若干个具有相当难度的猜想和公开问题。在第二章中,我们考虑了组合群试领域内由Erdos,Frankl和Furedi提出的、具有三十年历史的一个猜想。给定n个被测样本,其中最多有d个是阳性的,群试理论的目标是采用尽可能少的测试次数找到所有阳性样本,而不是仅仅对所有样本进行逐个检测。一个二元矩阵被称为是d-分离的,如果它的任意d列的布尔和都不包含其它列。分离矩阵在非自适性群试中有着极为重要的应用。用T(d)表示最小的t,使得存在一个满足n t × rn的d-分离矩阵。前人已证明T(?)并猜测T(d)≥ (d+1)2。通过技巧性地利用Erdos和Gallai经典的图匹配定理,我们证明(?),缩小了与猜想值之间的鸿沟。在第三章中,我们考虑了防诬陷码、父代识别码与追踪码的上界。这些码都是被用来保护具有版权的数字文件的。它们在诸如数字指纹、广播加密方案等场景中都有应用。利用一些组合计数方法中的技巧,我们分别给出了这三种码的上界。这些界都是目前已知的最优界。在第四章中,我们研究了一个重要的图兰问题,即Brown, Erd6s和S6s提出的稀疏超图问题。考虑n个顶点上的r-均衡超图,设其不含仅由v个顶点张成的e条边,四十多年前,Brown等人用函数fr(n,u,e)来表示这个超图所能含有的最大边数。他们提出了一个著名猜想:(?)对所有整数r k ≥ 2,e ≥ 3都成立。注意到,当r=3,e = 3,k = 2时,该猜想的正确性是由著名的Ruzsa-Szemeredi的(6,3)-定理所保证的。我们为该猜想的成立提供了更多的证据。一方面,我们用超图移除引理证明:猜想的右边对所有固定的整数r ≥ k + 1 ≥ e ≥ 3都成立。我们的结果涵盖了历史上达到猜想上界的所有已知情形。另一方面,通过构造一个合适的加法数论中的sum-free集,我们说明:猜想的左边对r≥3,k = 2与e = 4,5,7,8都成立。在e≥4且r≥ 4的范围内,我们的构造是第一个使猜想下界成立的构造。可分哈希族是一种非常有用的组合结构,它是组合学、密码学和编码理论中很多研究对象的推广。在第五章中,我们解决了关于可分哈希族和完美哈希族的上下界的若干公开问题和猜想。首先,我们发现可分哈希族的大小满足一种Johnson型的迭代不等式。从此出发,我们给出了可分哈希族的改进上界。其次,我们构造了一类完美哈希族的无穷类。它不仅正面回答了 Bazrafshan和Trung关于可分哈希族的一个公开问题,而且回答了 Alon和Stav关于父代识别码的一个猜想。最后,用表示(N,q)表示q元N长强度为t的完美哈希族的最大可能大小。Walker和Colbourn猜测当q充分大时有p3(3,q) = o(q2)。通过使用(6,3)-定理,我们证明了(?)。此外,利用一些加法数论的工具,我们还证明了(?)。在第六章和第七章里,我们分别研究了信息科学中的两个编码问题。第一个问题是集中式缓存编码方案,它是由Maddah-Ali和Niesen提出的一种技术,被用来降低无线网络系统中高峰时期的网络负载。设K是系统中用户的数目,则比率R(K)和复杂性F(K)是缓存方案的主要衡量指标。我们希望设计使R(K)和F(K)都尽量小的缓存方案。之前的结果都满足R(K)是常数而F(K)是指数函数。我们把这个问题与3-均衡3-部的(6,3)-free的超图的构造联系起来,并提出了第一个具有常数比率、亚指数复杂性的缓存方案。第二个问题是分布式存储码,它在现代存储系统中有着重要应用。Piggybacking设计被用来构造同时具有好的译码复杂性与修复带宽的存储码。通过引入一个新颖的piggybacking框架,我们所提出的piggyback码具有与现存的码相同的译码复杂性,但是使修复带宽率从r-1降低到了(?)。在第八章中,我们考虑了一个有限域上的极值问题。最近,Croot-Lev-Pach和Ellenberg-Gijswijt使用了一种新颖的多项式方法,分别界定了Z4n与F3n上不含3长等差数列的最大子集的大小,这两篇文章都发表在《Annals of Mathematics》上。Terence Tao总结了他们的工作,把其提炼为一种计算某些多变量函数的秩的方法。我们改变了Tao的计数公式,并用新公式来证明了如下结论:设q是一个固定的奇素数幂,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.
【学位授予单位】：浙江大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：O157

【相似文献】