Extremal Combinatorial Configurations Related To Several Problems Of Information Science

There is a long history of the interactions between information science and combinatoric-s. Information science provides problems and stimulates the development of combinatorics in a concrete applicational level while maturity of various fields of combinatorics offers theoretical supports to information scientific researches. Essentially, problems arising from information sci-ence may be turned into extremal configuration problems in combinatorics. This dissertation aims to investigate several problems arising from information science via a combinatorial perspective, with applications of tools from graph theory, probabilistic methods and extremal combinatorics.In Section 1, we will briefly introduce the backgrounds of several problems arising from information science and summarize our main contributions towards these problems.In Section 2, we will focus on permutation codes and snake-in-the-box codes in permuta-tion groups. These are widely used in areas such as power line communications, block ciphers and rank modulation schemes for flash memories. We turn the problem of analyzing the number of codewords into a graph theoretic problem and construct proper colorings of certain graphs to analyze the independence number. In this way we can improve the lower bound on the number of codewords for permutation codes under Hamming metric or Kendall’s τ-metric. The problem of snake-in-the-box codes under Kendall’s τ-metric differs significantly in permutation groups of odd or even order. In S2n+i we give a rigourous proof of a construction given by Horovitz and Etzion, and propose a better construction with a slight modification. In S2n+2 we get a nontrivial construction by merging several replicas of a snake in S2n+1, which is asymptotically optimal.In Section 3, we focus on collusion-secure codes and related hash families, arising from digital fingerprints. We turn the problem of deciding the number of codewords into a hypergraph theoretic problem and make use of results concerning the independence number of certain hypergraphs. In this way we improve the lower bounds of perfect hash families, frame-proof codes and separable codes with certain parameters. Our work is known to be the first application of this hypergraph approach.In Section 4, we analyze when an invertible binary matrix contains the largest ratio of 2 x 2 invertible submatrices. The original motivation of this purely combinatorial problem can be traced to the Turing Award winner Ron Rivest, who proposes all-or-nothing transforms, a preprocessing to add additional securities for block ciphers. Via integer programming and probabilistic analyses, we completely solve this problem and offer explicit constructions via cyclotomies.In Section 5, we focus on minimal size of unextendible product bases in a given multipartite Hilbert space, which is one of the most fundamental problems in quantum information theory and has wide applications in various areas of quantum information theory. We determine the precise value of the minimal size of unextendible product bases for some parameters, by applying sever-al graph-theoretic tools including orthogonal representations of graphs, connectivity of circulant graphs and 1-factorizations of graphs.In Section 6, we briefly introduce some other topics still under investigation.