Improved upper bounds for parent-identifying set systems and separable codes (Q2220762)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Improved upper bounds for parent-identifying set systems and separable codes |
scientific article |
Statements
Improved upper bounds for parent-identifying set systems and separable codes (English)
0 references
25 January 2021
0 references
A \(t\)-parent-identifying set system, or \(t\)-IPPS\((w,v)\), is a pair \((V,\mathcal{B})\) where \(V\) is a set of \(v\) elements and \(\mathcal{B}\) is a family of \(w\)-sized subsets of \(V\) with the property that, for any \(w\)-sized subset \(T\subseteq V\), either \[ P_t(T) = \emptyset\qquad\text{or}\quad \bigcap_{\mathcal{P}\in P_t(T)}\mathcal{P} \neq \emptyset\,, \] where \[ P_t(T) := \Big\{\mathcal{P}\subseteq \mathcal{B}\::\: |\mathcal{P}|\leq t\,,\;T\subseteq \bigcup_{B\in \mathcal{P}}B\Big\}\,. \] The author of this paper proves new upper bounds for \[ I_t(w,v) := \max\big\{|\mathcal{B}|\::\: (V,\mathcal{B}) \textrm{ is a \(t\)-IPPS\((w,v)\)}\} \] that sharpen several existing bounds in the literature. The authors generalises other existing results in the literature by proving that \(I_t(w,v) = v-w+1\) when \(w\leq \lfloor\frac{t^2}{4}+t\rfloor\). The author furthermore proves new and improved upper bounds for related combinatorial structures, the \(q\)-ary separable codes.
0 references
parent-identifying set systems
0 references
separable codes
0 references
\(B_2\) codes
0 references
distance distribution
0 references
0 references