报告人：葛根年教授，首都师范大学

时间：2016年10月27日（周四）下午3:00-4:00

地点：1518

题目：Centralized coded caching schemes, cover-free families and separating hash families related to extremal and additive combinatorics

摘要：A code can be regarded as a subset of its underlying base set satisfying some restrictions.The tools from extremal combinatorics or additive combinatorics have been found useful in the determination of bounds and constructions for various codes.

      In this talk, we will discuss several classes of discrete objects which have important applications in information science, for example, wireless network communication, DNA library screening and security protection. These objects include: centralized coded caching schemes, cover-free families, separating hash families and some related secure codes.

      Firstly, we establish an equivalence between centralized coded caching schemes and linear (6, 3)-free 3-uniform 3-partite hypergraphs. Two new constructions are also presented in this manner. Secondly, using a classical graph matching theorem of Erd˝os and Gallai, we study a well-known conjecture by Erd˝os-Frankl-F¨uredi on an old problem of the disjunctive code theory and obtain a best known lower bound. Thirdly, we solve several open problems and conjectures for separating hash families and related secure codes, which include: Bazrafshan-Trung’s open problem on separating hash families, Alon-Stav’s conjecture on parent-identifying codes, and Walker-Colbourn’s conjecture on perfect hash families. In addition, we also approve partially a question of Blackburn-Etzion-Stinson-Zaverucha on perfect hash families