The Application Of The Extremal Combinatorial Methods In Several Problems Of Information Science

Combinatorics has a close connection with information science. On one hand, combinatorics provides the theoretical supports for the study of information science. On the other hand, a variety of problems arising from information science stimulate the rapid development of combinatorics.Extremal combinatorics is one of the most active branches of combinatorics in recent decades.Simultaneously it has the closest interaction with information science. This dissertation aims to use the basic methods of extremal combinatorics to study several problems arising from information science and give some improvements.In Chapter 1, we will briefly introduce the backgrounds of the problems concerned, and sum-marize our main contributions to these problems.In Chapter 2, we focus on the construction of the circulant compressed sensing matrix. The construction of the compressed sensing matrix is one of the most important problems in signal processing. We will use the estimation of the partial exponential sum to give the construction of the circulant matrices, which not only achieve the theoretic bound but also perform well in storage and computation.In Chapter 3, we focus on the theory of multiply constant-weight codes. Multiply constant-weight codes establish the connection between the design of the Loop physically unclonable func-tions and coding theory. We give a new upper bound for multiply constant-weight codes through the sphere codes, which improves the Johnson bound. By the tool of the graph decomposition, we show the existence of two classes of optimal multiply constant-weight codes.In Chapter 4, we consider the problem about L-intersection from extremal set system. We use the linear algebra method, including incidence matrix and multilinear polynomial, to improve the estimation of Alon-Babai-Suzuki inequality.In Chapter 5, we focus on the construction of the PIR array codes. A scheme with a small number of servers is of great interest due to applicable reasons. We use the idea from combinatorial designs to construct the optimal PIR array code with the minimal number of servers. Meanwhile,we give a new upper bound for PIR array codes.In Chapter 6, we summarize the other works while pursuing the doctor degree.