Some intriguing upper bounds for separating hash families

• 来源期刊: 中国科学：数学（英文版）
• 年，卷（期）: 2019,（2）
• 页码范围: 269-282
• 页数: 14页
• 语种: 英文

摘要

An N × n matrix on q symbols is called {w1,…,wt }-separating if for arbitrary t pairwise disjoint column sets C1,…,Ct with ｜Ci｜ =wi for 1 ≤ i ≤ t,there exists a row f such that f(C1),…,f(Ct) are also pairwise disjoint,where f(Ci) denotes the collection of components of Ci restricted to row f.Given integers N,q and w1,…,wt,denote by C(N,q,{w1,…,wt}) the maximal n such that a corresponding matrix does exist.The determination of C(N,q,{w1,…,wt }) has received remarkable attention during the recent years.The main purpose of this paper is to introduce two novel methodologies to attack the upper bound of C(N,q,{w1,…,wt }).The first one is a combination of the famous graph removal lemma in extremal graph theory and a Johnson-type recursive inequality in coding theory,and the second one is the probabilistic method.As a consequence,we obtain several intriguing upper bounds for some parameters of C(N,q,{w1,…,wt }),which significantly improve the previously known results.