信息科学与组合数学的交叉历来已久。信息科学在具体应用层面刺激着组合数学的发展,组合数学的体系的日臻成熟为信息科学的研究提供了理论支撑。信息科学中的若干问题,本质上都可以转化为一些组合数学中的极值构型问题。本学位论文将从组合数学的观点出发,融汇应用了图论、概率方法、极值组合等相关工具,对若干信息科学中的问题进行了一定的思考与推进。在第1章绪论部分,我们将简要介绍本文所涉及的各信息科学问题的相关背景,并概述本文对此问题所做的推进工作。在第2章中,我们的研究对象为置换群上的置换码与蛇形码,它们在电力线技术、分组密码、闪存中的排序调制等领域有着广泛应用。我们将对码字数目的研究转化为图论上的问题,通过构造合适的染色方案给出了图的独立数,进而分别改进了汉明距离和Kendall’s τ-距离下的置换码的下界。Kendall’s τ-距离下的蛇形码问题在奇数阶置换群和偶数阶置换群上有明显的区别。在S2n+1上我们严格证明了’Horovitz-Etzion构造”的可行性,并在其基础上进行微调得到了更优的蛇形码。在S2n+2上我们利用之前S2n+1中的蛇形码为基础进行复制与拼接,得到了非平凡的蛇形码构造,在渐进意义下达到最优。在第3章中,我们的研究对象为源于数字产品版权保护背景的合谋-安全码及相关哈希函数族。我们将对码字数目的研究转化为超图上的问题,进而借助超图的独立数的相关结论,改进了特定参数条件下完全哈希函数族、防诬陷码、可分离码的下界。这种利用超图模型的分析方法尚属首次。在第4章中,我们研究的问题是怎样的一个可逆二元矩阵中拥有最大比例的2×2可逆子矩阵。这个纯粹的组合问题的研究背景可追溯于图灵奖得主Ron Rivest为进一步加强分组密码的安全性所提出的一种预处理步骤—AONT变换。我们通过建立问题的整数规划,结合概率方法的分析,完全确定了此问题的最优解,并以分圆构造为基础给出了近似最优的矩阵构造方法。在第5章中,我们研究的问题为多部希尔伯特空间中的不可扩展乘积基的最小规模问题。此问题是量子信息学中的最基本问题之一,在量子信息的诸多领域有着广泛的应用。我们综合利用图的正交表示、循环图的连通性、图的1-因子分解等若干图论工具,决定了一系列参数下的最小规模UPB的大小的准确值。在第6章中对其它在研问题做了简要汇报。