2017/07/06 by Ge, Gennian, Shangguan, Chong, Wang, Xin · 1 citation
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1707.01758
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 attentions 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.