New bounds on parent-identifying codes: The case of multiple parents

Let C be a code of length n over an alphabet of q letters. A codeword y is called a descendant of a set of t codewords {x¹, . . . ,x ^t} if yi, ∈ {x_i¹, . . . ,x _i^t} for all i = 1, . . . , n. A code is said to have the Identifiable Parent Property of order t if, for any word of length n that is a descendant of at most t codewords (parents), it is possible to identify at least one of them. Let f_t(n,q) be the maximum possible cardinality of such a code. We prove that for any t,n,q, (c₁(t)q)^n/s(t) < f_t(n,q) < c₂(t)q^⌈n/s(t)⌉ where s(t) = ⌊(t/2 + 1)²⌋ - 1 and c₁(t), c ₂(t) are some functions of t. We also show some bounds and constructions for f₃(5,q). f₃(6,q), and f _t,(n,q) when n < s(t).