Sparse hypergraphs: from theory to applications
 发布时间： 2017-12-24     19:36   【返回上一页】 发布人：葛根年

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. 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/geq 2, e/geq 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 /geq k + 1 /geq e /geq 3$. On the other hand, we use tools from additive number theory to show that the lower bound is true for $r/geq 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 improved from exponential to sub-exponential.