Several Problems In Extremal Combinatorics And Coding Theory

This thesis involves various problems in the area of extremal combinatorics and coding theory.We use many powerful tools and deep including polynomial method,hypergraph removal lemma and additive number theory to attack several conjectures and open problems in the literature.In Chapter 2, we consider a thirty-year-old conjecture of Erdos, Frankl and Furedi in the combinatorial group testing theory. Given n items with at most d of which being positive, instead of testing these items individually, the group testing theory aims to identify all positive items using as few tests as possible. A binary matrix is called d-disjunct if the boolean sum of arbitrary d columns does not contain another column not in this collection. Disjunct matrices have important applications in the nonadaptive group testing. Let T(d) denote the minimal t such that there exists at × n d-disjunct matrix with n > t.It was known that T(d) ? (d+2 2), and was conjectured that T(d) > (d+1)2. Using a classical graph matching theorem of Erd6s and Gallai, we narrow the gap by proving (?).In Chapter 3, we consider the upper bounds of frameproof codes, parent-identifying codes and traceability codes. These codes are introduced to protect the copyrighted digital data. They have applications in the scenarios like digital fingerprinting and broadcast encryption schemes. Using skills from combinatorial counting method, we present three upper bounds for each of these codes.To the best of our knowledge, all the bounds are the best known ones.In Chapter 4, we deal with an important problem in Turan theory, namely, the sparse hyper-graph problem of Brown, Erd6s and Sos. More than forty years ago, they introduced the function fr(n,v,e) to denote the maximum number of edges in an r-uniform hypergraph on n vertices which does not contain e edges spanned by v vertices. They posed a well-known conjecture:(?) holds for all integers r > k ? 2, e ? 3. Note that for r = 3, e = 3, k = 2, this conjecture was solved by the famous Ruzsa-Szemeredi's (6,3)-theorem.We add more evidence for the validity of this conjecture. On one hand, we use the hypergraph removal lemma to prove that the right hand side is true for all fixed integers r?k+ 1?e?3.Our result implies all known upper bounds which match the conjectured magnitude. On the other hand, by constructing an appropriate sum-free set in additive number theory, we show that the left hand side is true for r ? 3, k = 2 and e = 4,5,7,8. Our construction provides the first lower bound which matches the conjecture in the range e > 4 and r > 4.Separating hash families are useful combinatorial structures which are generalizations of many well-studied objects in combinatorics, cryptography and coding theory. In Chapter 5, we solve several open problems and conjectures about the upper and lower bounds of separating hash families and perfect hash families. Firstly, we discover that the cardinality of a separating hash family satisfies a Johnson-type recursive inequality. As a result, we obtain a new upper bound,which is superior to all previous ones. Secondly, we present a construction for an infinite class of perfect hash families. It provides an affirmative answer to both Bazrafshan-Trung's open problem on separating hash families and Alon-Stav's conjecture on parent-identifying codes. Thirdly, let pt(N, q) denote the maximal cardinality of a t-perfect hash family of length N over an alphabet of size q. Walker and Colbourn conjectured for sufficiently large q it holds that p3(3,q) = o(q2). We verify this conjecture by proving (?) Our proof can be viewed as an appli-cation of the (6,3)-theorem. We also prove (?), using tools from additive number theory.In Chapters 6 and 7, we study two coding problems in the area of information sciences, respec-tively. The first one is the centralized coded caching scheme, which is proposed by Maddah-Ali and Niesen as a technique to reduce the network burden in peak times in a wireless network sys-tem. The rate R(K) and the complexity F(K) are two major evaluating indicators for a caching scheme, where K is the number of users. The goal is to design caching schemes with R(K) and F(K) both as small as possible. Previous caching schemes have constant R(K) and exponential F(K).We relate this problem to the construction of 3-uniform 3-partite (6,3)-free hypergraphs and present the first caching scheme in the literature, which has constant rate and sub-exponential complexity. The second one is the distributed storage codes, which have important applications in the design of modern storage systems. Piggybacking design is a strategy to construct storage codes with both good decoding complexity and repair bandwidth. By introducing a novel piggybacking framework, we present a piggyback code which has the same decoding complexity as the previous one, while the repair bandwidth rate is reduced from (?)In Chapter 8, we discuss an extremal problem over the finite fields. Recently. Croot-Lev-Pach and Ellenberg-Gijswijt used a novel polynomial method to give upper bounds for three-term arith-metic progression free sets in Z4n and F3n, respectively. These two papers have been published in"Annals of Mathematics". Their method was summarized by Terence Tao as a principal which counts the slice-ranks of certain multi-variable polynomials. We develop a variant of Tao's count-ing formula and use it to prove that, if q is a fixed odd prime power, then the maximal cardinality of a subset A of Fqn with no three distinct elements x,y,z ? A satisfying (?). This bound substantially improves the previously known bound (?) for fixed q and sufficiently large n.