Sparse Hypergraphs: from Theory to Applications

      More than forty years ago, Brown, Erdős and Sós introduced the function f_r( 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. Together with Alon and Shapira, they posed a well-known conjecture: n ^{k-o (1)} < f_r( n, e( r-k) +k+1 , e) = o( n^k) 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-Szemerédi’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 upper bound is true for all fixed integers r ≥ k + 1 ≥ e ≥ 3. On the other hand, we use tools from additive combinatorics to show that the lower bound is true for
r ≥ 3, k = 2 and e = 4, 5, 7, 8.
    We also use the theory of sparse hypergraphs to attack several open problems and conjectures in cryptography and coding theory. For example, we use the (6,3)-theorem to solve a conjecture of Walker and Colbourn on perfect hash families. This conjecture had been open for ten years and traditional methods seem to have limited effect on it. We also use the (6,3)-free hypergraphs to construct two classes of placement delivery arrays which are useful for centralized coded caching. The complexity of the PDAs is reduced from exponential to sub-exponential.