本论文考虑了极值组合与编码理论中的若干问题。通过使用包括多项式方法、超图移除引理、加法数论在内的强有力的数学工具,研究了若干个具有相当难度的猜想和公开问题。在第二章中,我们考虑了组合群试领域内由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满足