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 ...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+3 种基金Beijing Hundreds of Leading Talents Training Project of Science and TechnologyBeijing Municipal Natural Science FoundationThe third author was supported by the Post-Doctoral Science Foundation of China(Grant No. 2018M632356)National Natural Science Foundation of China (Grant No. 11801392)
文摘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.
