摘要
An N ×n matrix on q symbols is called {w_1,...,w_t}-separating if for arbitrary t pairwise disjoint column sets C_1,..., C_t with |C_i|=w_i for 1 ≤i≤t, there exists a row f such that f(C_1),...,f(C_t) are also pairwise disjoint, where f(C_i) denotes the collection of componentn of C_i restricted to row f. Given integers N, q and w_1,...,w_t, denote by C(N,q,{w_1,...,w_t}) the maximal a such that a corresponding matrix does exist.The determination of C(N,q,{w_1,...,w_t}) 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, {w_1,...,w_t}).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 onc is the probabilistic method. As a consequence, we obtain several intriguing upper bounds for some parameters of C(N,q,{w_1,...,w_t}), which significantly improve the previously known results.
An N ×n matrix on q symbols is called {w_1,...,w_t}-separating if for arbitrary t pairwise disjoint column sets C_1,..., C_t with |C_i|=w_i for 1 ≤i≤t, there exists a row f such that f(C_1),...,f(C_t) are also pairwise disjoint, where f(C_i) denotes the collection of componentn of C_i restricted to row f. Given integers N, q and w_1,...,w_t, denote by C(N,q,{w_1,...,w_t}) the maximal a such that a corresponding matrix does exist.The determination of C(N,q,{w_1,...,w_t}) 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, {w_1,...,w_t}).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 onc is the probabilistic method. As a consequence, we obtain several intriguing upper bounds for some parameters of C(N,q,{w_1,...,w_t}), which significantly improve the previously known results.
基金
supported by National Natural Science Foundation of China (Grant Nos. 11431003 and 61571310)
Beijing Scholars Program
Beijing Hundreds of Leading Talents Training Project of Science and Technology
Beijing Municipal Natural Science Foundation
The third author was supported by the Post-Doctoral Science Foundation of China(Grant No. 2018M632356)
National Natural Science Foundation of China (Grant No. 11801392)
